30. 串联所有单词的子串，31. 下一个排列 ，32. 最长有效括号，每题做详细思路梳理，配套Python&Java双语代码， 2024.03.15 可通过leetcode所有测试用例。
30. 串联所有单词的子串
给定一个字符串
s和一个字符串数组words。words中所有字符串 长度相同。
s中的 串联子串 是指一个包含words中所有字符串以任意顺序排列连接起来的子串。
- 例如，如果
words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"， 和"efcdab"都是串联子串。"acdbef"不是串联子串，因为他不是任何words排列的连接。返回所有串联子串在
s中的开始索引。你可以以 任意顺序 返回答案。
示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9]解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。 输出顺序无关紧要。返回 [9,0] 也是可以的。示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]输出：[]解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。 s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。 所以我们返回一个空数组。示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12] 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
解题思路
-
理解问题：给定一个主字符串
s和一个字符串数组words。words中所有字符串长度相同。需要找到s中所有包含words中所有字符串以任意顺序连接形成的子串的起始索引。 -
初始化：由于
words中的所有字符串长度相同，我们可以计算出每个串联子串的总长度，即wordLength * words.size()。接下来，我们可以在主字符串s中遍历长度为此值的所有子串。 -
滑动窗口：使用滑动窗口的方法来检查
s中的每个可能的子串。窗口大小为串联子串的总长度。 -
哈希表：使用两个哈希表，一个用来存储
words数组中单词的出现次数，另一个用来存储当前窗口中与words中单词相匹配的单词出现次数。 -
遍历：从
s的第0个字符开始，遍历到s.length() - windowSize为止。对于每个可能的子串，使用哈希表来检查是否包含了words中所有单词的正确数量。如果是，则将当前子串的起始索引添加到结果列表中。 -
返回结果：遍历完成后，返回所有找到的起始索引。
完整代码
Java
public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (s == null || s.length() == 0 || words == null || words.length == 0) {
return result;
}
int wordLen = words[0].length();
int windowLen = wordLen * words.length;
Map<String, Integer> wordMap = new HashMap<>();
for (String word : words) {
wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
}
for (int i = 0; i <= s.length() - windowLen; i++) {
Map<String, Integer> seenWords = new HashMap<>();
int j = 0;
while (j < words.length) {
String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
if (wordMap.containsKey(word)) {
seenWords.put(word, seenWords.getOrDefault(word, 0) + 1);
if (seenWords.get(word) > wordMap.get(word)) {
break;
}
} else {
break;
}
j++;
}
if (j == words.length) {
result.add(i);
}
}
return result;
}
}Python
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words:
return []
word_length = len(words[0])
word_count = len(words)
window_length = word_length * word_count
word_map = {}
for word in words:
if word in word_map:
word_map[word] += 1
else:
word_map[word] = 1
results = []
for i in range(len(s) - window_length + 1):
seen_words = {}
for j in range(0, window_length, word_length):
word = s[i + j:i + j + word_length]
if word in word_map:
if word in seen_words:
seen_words[word] += 1
else:
seen_words[word] = 1
if seen_words[word] > word_map[word]:
break
else:
break
else:
results.append(i)
return results
31. 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
- 例如，
arr = [1,2,3]的下一个排列是[1,3,2]。- 类似地，
arr = [2,3,1]的下一个排列是[3,1,2]。- 而
arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。给你一个整数数组
nums，找出nums的下一个排列。必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3] 输出：[1,3,2]示例 2：
输入：nums = [3,2,1] 输出：[1,2,3]示例 3：
输入：nums = [1,1,5] 输出：[1,5,1]
解题思路
-
从右向左查找：首先从数组的末尾开始向前查找，找到第一个不满足递增关系的元素，记为
nums[i]。这意味着从nums[i+1]到nums[n-1]（其中n是数组的长度）这部分是按降序排列的。 -
查找交换位置：如果找到了这样的
nums[i]，再次从数组的末尾开始向前查找，找到第一个大于nums[i]的元素，记为nums[j]。 -
交换元素：交换
nums[i]和nums[j]。 -
反转子数组：最后，将从
i+1到数组末尾的部分反转，因为原来这部分是降序的，反转之后变为升序，这样就可以得到下一个排列。
如果整个数组都是降序排列的，那么它已经是最大的排列，按照题目要求，应该重排为最小排列，即其元素按升序排列。这可以通过直接反转整个数组来实现。
完整代码
Java
public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
}
Python
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# Step 1: 从右向左找到第一个不是递增的数字
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
# Step 2: 如果找到了这样的数字，再找一个比它大的最小数字进行交换
if i >= 0:
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
# 交换这两个数字
nums[i], nums[j] = nums[j], nums[i]
# Step 3: 将 i 之后的数字反转，确保是下一个最小的排列
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left, right = left + 1, right - 132. 最长有效括号
给你一个只包含
'('和')'的字符串，找出最长有效（格式正确且连续）括号子串
的长度。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"示例 3：
输入：s = "" 输出：0
解题思路
我们可以使用栈。栈可以帮助我们跟踪未匹配的括号，并且可以用来找出有效子串的长度。具体的做法如下：
-
初始化：创建一个栈，并将
-1推入栈中。这一步是为了在一开始时，栈底有一个元素，便于后面计算长度。 -
遍历字符串：遍历给定字符串的每个字符。
- 如果当前字符是
'('，将其索引推入栈中。 - 如果当前字符是
')'，首先弹出栈顶元素。- 如果此时栈变为空，将当前索引推入栈中。这是因为这个右括号可能是下一个有效子串的起始点的前一个位置。
- 如果栈不为空，则计算当前有效子串的长度，方法是当前索引减去栈顶元素。更新最长有效括号子串的长度。
- 如果当前字符是
-
返回结果：在遍历完整个字符串后，最长有效括号子串的长度就被找到了。
完整代码
Java
public class Solution {
public int longestValidParentheses(String s) {
int maxLength = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1); // 初始时压入-1，便于后续计算长度
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i); // 将左括号的索引压入栈中
} else {
stack.pop(); // 遇到右括号，弹出栈顶元素
if (stack.isEmpty()) {
stack.push(i); // 如果栈为空，压入当前索引作为新的基准
} else {
maxLength = Math.max(maxLength, i - stack.peek()); // 计算当前有效子串长度
}
}
}
return maxLength;
}
}Python
class Solution:
def longestValidParentheses(self, s: str) -> int:
max_length = 0
stack = [-1]
for i, char in enumerate(s):
if char == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
max_length = max(max_length, i - stack[-1])
return max_length
