反转字符串
344. 反转字符串 - 力扣（LeetCode）
将输入的字符串反转，要求不给另外的数组分配额外的空间，必须原地修改输入数组、使用O(1)的额外空间解决这一问题
双指针：指向首尾，每次交换，同时移动，直至相遇
1
2
3
4
5
6
7
8
|
func reverseString(s []byte) {
idx1, idx2 := 0, len(s)-1 // 俩指针分别指向首尾
for idx1 < idx2 {
s[idx1], s[idx2] = s[idx2], s[idx1] // 交换值
idx1++ // 后移
idx2-- // 前移
}
}
|
反转字符串 II
541. 反转字符串 II - 力扣（LeetCode）
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于
k 个，则将剩余字符全部反转。
- 如果剩余字符小于
2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样
双指针：快指针遍历字符串，当快指针计数至2k或结束，慢指针指向这2k个字符的开头或剩余字符的开头，反转后，更新慢指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
func reverseStr(s string, k int) string {
slowIdx := 0 // 慢指针指向首
sArr := []byte(s) // 字符串转为字符数组
for fastIdx := 0; fastIdx < len(sArr); fastIdx++ { // 快指针遍历数组
if (fastIdx+1)%(2*k) == 0 { // 计数至2k个字符
reverse(sArr[slowIdx : slowIdx+k]) // 反转这2k字符中的前k个字符
slowIdx = fastIdx + 1 // 更新慢指针
}
}
if len(sArr)-slowIdx < k { // 剩余字符少于k个
reverse(sArr[slowIdx:]) // 反转剩余全部字符
} else if len(sArr)-slowIdx >= k && len(sArr)-slowIdx < 2*k { // 剩余字符少于2k但大于或等于k个
reverse(sArr[slowIdx : slowIdx+k]) // 反转前k个字符
}
return string(sArr)
}
// 反转给定的字符串
func reverse(s []byte) {
idx1, idx2 := 0, len(s)-1 // 俩指针分别指向首尾
for idx1 < idx2 {
s[idx1], s[idx2] = s[idx2], s[idx1] // 交换值
idx1++ // 后移
idx2-- // 前移
}
}
|
优化：遍历字符串时每次前进2*k个字符，也就是到了下一个2k的第一个字符；进入循环后判断当前2k的第一个字符加上k个字符后是否超过数组长度，若没超过，则反转i开始的前k个字符，若超过了，反转i开始的全部字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func reverseStr(s string, k int) string {
sArr := []byte(s) // 将字符串转为字符数组
for i := 0; i < len(sArr); i += 2 * k { // 步进2*k
if i+k <= len(sArr) { // i加上k个字符后没超过数组长度
reverse(sArr[i : i+k]) // 反转i开始前k个字符
} else { // i加上k个字符后超过数组长度
reverse(sArr[i:]) // 反转i开始全部字符
}
}
return string(sArr)
}
func reverse(s []byte) {
idx1, idx2 := 0, len(s)-1
for idx1 < idx2 {
s[idx1], s[idx2] = s[idx2], s[idx1]
idx1++
idx2--
}
}
|
替换数字
54. 替换数字（第八期模拟笔试） (kamacoder.com)
给定一个字符串，包含小写字母和数字字符，要求将每个数字字符替换为number
开辟一个新的空间，遍历给定字符串，遇到字母就存入结果集，遇到数字就将number存入结果集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
package main
import "fmt"
func main() {
var strByte []byte
fmt.Scanln(&strByte)
res := ""
for _, v := range strByte { // 遍历字符串
if v >= 'a' && v <= 'z' { // 遍历到小写字母
res += string(v) // 追加到结果集
} else { // 遍历到数字字符
res += "number"
}
}
fmt.Println(res)
}
|
反转字符串中的单词
151. 反转字符串中的单词 - 力扣（LeetCode）
给定一个字符串，用空格分隔字符串中的单词，给定的字符串中可能有前导空格、尾随空格或者单词间的多个空格。返回反转单词后的字符串，且单词间应当仅用单个空格分隔也不包含任何额外的空格
思路：双指针：从右向左遍历给定字符串，一对指针确定一个单词；当快指针遇到非空格字符且慢指针指向空格时，说明找到单词尾，此时更新慢指针，用慢指针标记单词尾；当快指针遇到空格字符且慢指针指向非空格字符时，说明遍历完了一个单词，将该单词存入结果集，更新慢指针指向当前快指针（空格），继续找下一单词；最后判断字符串首是否还有最后一个单词
注意：
- 当字符串首字符非空格时，快指针会因为无法遍历到为空格从而记录不到首单词，因此要将首字符的单词判断存在后加入
s 包含英文大小写字母、数字和空格 ' '，数字也算单词- 在ASCII中0值最小，z值最大，0~z中包括所有大小写字符且不含空格，有特殊字符，但题目中说明不含特殊字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
func reverseWords(s string) string {
res := []byte{}
// 慢指针初始指向末尾
slow := len(s) - 1
// 快指针倒序遍历字符串
for fast := len(s) - 1; fast >= 0; fast-- {
// 判是否为单词尾
if s[fast] != ' ' && s[slow] == ' ' {
// 更新慢指针指向单词尾
slow = fast
} else if s[fast] == ' ' && s[slow] != ' ' {
// fast遍历到单词首
// 当前单词追加到加入结果集
res = append(res, []byte(s[fast:slow+1])...)
// 更新慢指针指向空格
slow = fast
}
}
// 判是否存在首字符的单词
if s[0] != ' ' {
res = append(res, ' ')
res = append(res, []byte(s[:slow+1])...)
}
// 去除首空格后返回
return string(res[1:])
}
|
右旋字符串
55. 右旋字符串（第八期模拟笔试） (kamacoder.com)
给定一个字符串和一个整数k，将字符串尾部k个字符移动到字符串首
先选定要移动的子串，然后字符串后移k个单位，再将选定子串放入字符串首
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
package main
import "fmt"
func main() {
var k int
fmt.Scanln(&k)
var s []byte
fmt.Scanln(&s)
temp := make([]byte, k)
copy(temp, s[len(s)-k:len(s)]) // 保存要移动的子串
for i := len(s) - 1; i >= k; i-- { // 字符后移
s[i] = s[i-k]
}
for i := 0; i < k; i++ {
s[i] = temp[i]
}
fmt.Println(string(s))
}
|
找出字符串中第一个匹配项的下标
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
给定两个字符串，找出第二个字符串在第一个字符串中的下标，若没有则返回-1
思路一：暴力，外层遍历第一个字符串，若遇到字符与第二个字符串首字符相同，则继续比较后续字符，若遇到不一样的，则进入下一外层循环，若外层遍历结束仍未找到，返回-1
写法一(推荐)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func strStr(haystack string, needle string) int {
i, j := 0, 0
for ; i <= len(haystack)-len(needle); i++ {
for j = 0; j < len(needle); j++ {
if haystack[i+j] != needle[j] {
break
}
}
if j == len(needle) {
return i
}
}
return -1
}
|
写法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func strStr(haystack string, needle string) int {
for i := 0; i <= len(haystack)-len(needle); i++ {
if haystack[i] == needle[0] { // 首字符相同
idx := i // 初始化指针指向字符串1的i
isOk := true // 默认匹配
for j := 0; j < len(needle); j, idx = j+1, idx+1 {
if haystack[idx] != needle[j] {
isOk = false // 不匹配
break
}
}
if isOk {
return i // 返回下标
}
}
}
return -1
}
|
- 时间复杂度：O(n × m)
- 空间复杂度：O(1)
思路二：KMP
该讲解更易理解：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/575568/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86
KMP，在一个串中查找是否出现过另一个串
KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。next数组用来记录已经匹配的文本内容，是KMP的重点。next数组就是一个前缀表（prefix table），前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配
为了清楚了解前缀表的作用，举一个例子：要在主串 aabaabaafa 中查找是否出现过一个模式串 aabaaf。主串中第六个字符 b 和模式串的第六个字符 f 不匹配了。如果是暴力匹配，此时模式串就要从头开始和主串起始的下一个字符匹配了，但如果使用前缀表，模式串就可以不从头匹配，而是从上次已经匹配的内容开始匹配，找到模式串中第三个字符 b 继续开始与主串第六个字符 b 匹配，因为主串第六个字符 b 之前的 aa 已经在上次匹配成功，主串也不会回退，直接从当前匹配不成功的地方继续比较
模式串的前缀表元素表示：下标之前（包括下标）的字符串中，相同前后缀的长度，当模式串与主串不匹配时，模式串直接跳到前一个字符的前缀表的所存下标开始与当前主串字符重新匹配。
KMP 相比于暴力更快的原因：
-
KMP 利用模式串已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配
-
KMP 的主串指针不会进行回溯
构建 next 数组：双指针。初始化慢、快指针分别指向模式串第一个和第二个元素，快指针遍历模式串；当快慢指针指向元素不同且慢指针指向非首时，慢指针循环回退，回退到前一个元素的 next 元素值；当快慢指针指向元素相同时，慢指针向右移动一个单位，最后设置当前快指针位置的 next 数组元素值为慢指针所在位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
func strStr(haystack string, needle string) int {
// 填充next数组
next := make([]int, len(needle))
i := 0 // 初始前缀末尾指针指向字符串首
for j := 1; j < len(needle); j++ { // 后缀末尾指针从第二个元素开始遍历
for i != 0 && needle[i] != needle[j] { // 俩指针指向值不同且前缀指针不在首
i = next[i-1] // 前缀指针回退
}
if needle[i] == needle[j] { // 俩指针指向值相等
i++ // 前缀指针前进
} // 若是前缀指针到首则不前进
next[j] = i // 前缀指针指向下标赋值给next数组
}
// 在z串中匹配模式串
i = 0 // i指向模式串首
for j := 0; j < len(haystack); j++ { // j指向主串
for i != 0 && haystack[j] != needle[i] { // 主串与模式串字符不相等
i = next[i-1] // 模式串指针回退
}
if haystack[j] == needle[i] { // 主串与模式串字符相等
i++ //模式串前进
}
if i == len(needle) { // 遍历完模式串
return j - len(needle) + 1 // 返回主串中匹配到的模式串首
}
}
return -1
}
|
- 时间复杂度：O(n+m)，n为文本串长度，m为模式串长度，匹配过程中文本串的遍历是没有回退过的，所以是O(n)，生成next数组需要遍历一遍模式串，所以时间复杂度是O(m)，综上整个KMP算法的时间复杂度是O(n+m)的
- 空间复杂度: O(m)
重复的子字符串
459. 重复的子字符串 - 力扣（LeetCode）
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成
暴力：若能被子串构成，则子串是从第一个字符开始的，且子串结束位置不大于中间位置，所以两层for循环，外层遍历获取子串的终止位置，内层遍历判断能否构成主串
注意：要记得判断最后剩余字符数不足以匹配子串的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func repeatedSubstringPattern(s string) bool {
for i := 0; i < len(s)/2; i++ { // i指向子串末尾,遍历到中间位置
isTrue := true // 默认该子串能构成主串
for j := i + 1; j < len(s); j += i + 1 { // j从第二个子串首开始遍历字符串,j每次前进子串长度
if len(s)-j < i || s[j:j+i+1] != s[:i+1] { // 子串与主串不匹配(包括最后剩余字符数不足以匹配)
isTrue = false // 该子串无法构成主串
break // 跳出循环,更新子串
}
}
if isTrue {
return true
}
}
return false
}
|
最后一个单词的长度
58. 最后一个单词的长度 - 力扣（LeetCode）
给定一个字符串，包含空格和连续字符，返回最后一个连续字符的长度
思路：从后向前遍历，找到最后一个字符的位置，向前遍历确定最后一个单词的首字符位置，记录该长度后返回
注意：
- 计数变量需要一开始就初始化，不能在计数循环内初始化，防止最后一单词首字符前再无字符或空格，直接结束循环，无法返回该计数变量
- 找到最后一个字符的位置并计数结束后需要跳出遍历循环，防止字符串继续计数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
func lengthOfLastWord(s string) int {
cnt := 0
// 倒序遍历
for i := len(s) - 1; i >= 0; i-- {
// 找到最后一个字符
if s[i] != ' ' {
// 向前遍历该单词
for j := i; j >= 0; j-- {
if s[j] == ' ' {
return cnt
} else {
cnt++
}
}
// 跳出循环
break
}
}
return cnt
}
|
最长公共前缀
14. 最长公共前缀 - 力扣（LeetCode）
给定一个字符串数组，返回最长公共前缀
思路：
- 初始化第一个字符串为最长公共前缀
- 从第二个字符串遍历给定字符串数组
- 取当前最长公共前缀长度 与 当前字符串长度 的最小值，逐个字符比较当前字符串与当前最长公共前缀
- 每次比较完取min(部分匹配成功, 全部匹配成功)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func longestCommonPrefix(strs []string) string {
// 初始化第一个字符串为最长公共前缀
res := strs[0]
// 从第二个字符串遍历给定字符串数组
for i := 1; i < len(strs); i++ {
// min(当前最长公共前缀长度, 当前字符串长度)
minlength := min(len(res), len(strs[i]))
// 逐个字符比较当前字符串与当前最长公共前缀
for j := 0; j < minlength; j++ {
// 判对应位置字符是否相同
if strs[i][j] != res[j] {
// 更新最长公共前缀
res = res[:j]
// 结束该字符比较
break
}
}
// res取min(部分匹配成功, 全部匹配成功)
res = res[:min(len(res), minlength)]
}
return res
}
|
Z 字形变换
6. Z 字形变换 - 力扣（LeetCode）
给定一个字符串和一个整数表示行数，将该字符串按上到下、从左到右的Z字形排列，返回从左往右逐行读取的字符串
思路一：利用二维矩阵模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
func convert(s string, numRows int) string {
if numRows == 1 {
return s
}
res := make([][]byte, numRows)
// 标记当前行
curRow := 0
// 标记当前是否为从上往下
isDown := true
// 遍历给定字符串将各字符追加到对应行
for i := 0; i < len(s); i++ {
// 将当前字符追加到对应行
res[curRow] = append(res[curRow], s[i])
// 更新行数
if curRow == numRows-1 {
curRow--
isDown = false
} else if curRow == 0 {
curRow++
isDown = true
} else if isDown {
curRow++
} else {
curRow--
}
}
// 遍历各行
resRow := ""
for _, row := range res {
resRow += string(row)
}
return resRow
}
|
思路二：直接构造
向下填写 numRows 个字符，然后向右上继续填写 numRows−2 个字符，最后回到第一行，因此 Z 字形变换的周期 t = r+r−2 = 2r−2，每个周期会占用矩阵上的 1+r−2 = r−1 列
- 记周期长度为
t，t=2(numRows−1)
- 记各周期第一个字符
(P, I, N)在原字符串中的下标为 j，j 依次为 0,t,2t,...
- 那么以图中字符
S 为例，当前行数为 i
- 设顶部字符
I 的下标为 j，实际为 t
- 则
S 的下标为 j+i，与 S 同周期同行的 I 的对应下标为 j+t-i
注意：同一周期内每行可能有两个字符，也可能只有一个
那么可以枚举行数 i，再嵌套枚举 j，得到每行的字符，直接放入待返回的字符串尾部即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func convert(s string, numRows int) string {
if numRows == 1 {
return s
}
res := make([]byte, 0, len(s))
// 周期长度
t := 2*numRows - 2
// 枚举行数i
for i := 0; i < numRows; i++ {
// 枚举每个周期的起始下标
for j := 0; j+i < len(s); j += t {
// 将当前周期的当前行的从左往右的第一个元素追加到结果集
res = append(res, s[j+i])
// 判非当前周期首行、末行且未越界元素
if i > 0 && i < numRows-1 && j+t-i < len(s) {
// 将当前周期的当前行的从左往右的第二个元素追加到结果集
res = append(res, s[j+t-i])
}
}
}
return string(res)
}
|
文本左右对齐
给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
要求：
- 尽可能多地往每行中放置单词。必要时可用空格
' ' 填充，使得每行恰好有 maxWidth 个字符。
- 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
- 文本的最后一行应为左对齐，且单词之间不插入额外的空格
思路：模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
func fullJustify(words []string, maxWidth int) []string {
res := make([]string, 0)
tempRow := make([]byte, 0, maxWidth)
spaceIdx := make([]int, 0)
// 遍历给定字符串数组
i := 0
for i < len(words) {
// 判当前行能否放下该单词
if len(tempRow)+len(words[i]) <= maxWidth {
// 加入该单词
tempRow = append(tempRow, []byte(words[i])...)
// 判是否有位置加空格
if len(tempRow) < maxWidth {
tempRow = append(tempRow, ' ')
spaceIdx = append(spaceIdx, len(tempRow)-1)
}
// 判是否为最后一个单词
if i == len(words)-1 {
// 判当前行是否填充完毕
if len(tempRow) < maxWidth {
// 后面直接全部填充空格
n := len(tempRow)
for i := n; i < maxWidth; i++ {
tempRow = append(tempRow, ' ')
}
}
// 收集结果并返回
res = append(res, string(tempRow))
return res
} else {
// 当前单词已处理遍历下一单词
i++
}
} else if len(tempRow) <= maxWidth {
// 判当前行是否填充完
if len(tempRow) == maxWidth {
// 判当前行是否只有一个单词或最后一个字符不为空格
if len(spaceIdx) == 1 || tempRow[len(tempRow)-1] != ' ' {
res = append(res, string(tempRow))
tempRow = make([]byte, 0, maxWidth)
spaceIdx = make([]int, 0)
continue
}
}
// 放不下当前单词 需要补空格
// 判当前行最后一个字符是否为空格且不止这一个空格(非当前行唯一单词）
if len(spaceIdx) != 1 && tempRow[len(tempRow)-1] == ' ' {
// 去除最后一个单词后的空格
tempRow = tempRow[:len(tempRow)-1]
spaceIdx = spaceIdx[:len(spaceIdx)-1]
}
// 计算空位数
cnt := maxWidth - len(tempRow)
// 记录当前遍历到的空格位置
idx := 0
// 从左向右补空格
for cnt != 0 {
// 补一个空格
temp := append(tempRow[:spaceIdx[idx%len(spaceIdx)]], ' ')
tempRow = append(temp, tempRow[spaceIdx[idx%len(spaceIdx)]:]...)
// 更新后续空格位置
for j := idx % len(spaceIdx); j < len(spaceIdx)-1; j++ {
spaceIdx[j+1]++
}
idx++
cnt--
}
}
}
return []string{}
}
|
验证回文串
125. 验证回文串 - 力扣（LeetCode）
给定一个字符串，验证其是否为回文串，要求去除其中的非字母和数字字符，大小写字符视作一样
思路：双指针
- 将所有大写->小写
- 双指针遍历，遇到非字母数字则移动
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
func isPalindrome(s string) bool {
// 初始化双指针指向首尾
left, right := 0, len(s)-1
// 遍历字符串将所有大写字符转为小写字符
bs := []byte(s)
for i, v := range bs {
if v >= 'A' && v <= 'Z' {
bs[i] = v - 'A' + 'a'
}
}
// 双指针遍历字符串
for left < right {
// 判是否当前俩字符不相等
if bs[left] != bs[right] {
// 判是否有非字母数字字符
if bs[left] < '0' || (bs[left] > '9' && bs[left] < 'a') || bs[left] > 'z' {
left++
} else if bs[right] < '0' || (bs[right] > '9' && bs[right] < 'a') || bs[right] > 'z' {
right--
} else {
// 俩都为字母字符且不相等直接返回false
return false
}
} else {
// 俩字符相等继续比较
left++
right--
}
}
return true
}
|
两数之和 II - 输入有序数组
给定一个递增数组和一个整数，在数组中找到和为整数的两个数，返回这俩数的下标，存在唯一解，不能重复使用同意元素。要求常量级额外空间。
思路一：二分查找
先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func twoSum(numbers []int, target int) []int {
// 遍历找nums1
for i, nums1 := range numbers {
// 二分查找target - nums1
t := target - nums1
left, right := i+1, len(numbers)-1
for left <= right {
mid := left + (right-left)/2
if numbers[mid] == t {
return []int{i + 1, mid + 1}
} else if numbers[mid] < t {
left = mid + 1
} else {
right = mid - 1
}
}
}
return []int{}
}
|
思路二：双指针
初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func twoSum(numbers []int, target int) []int {
left, right := 0, len(numbers)-1
for left < right {
if numbers[left]+numbers[right] == target {
return []int{left + 1, right + 1}
} else if numbers[left]+numbers[right] < target {
left++
} else {
right--
}
}
return []int{}
}
|
串联所有单词的子串
30. 串联所有单词的子串 - 力扣（LeetCode）
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
- 例如，如果
words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
func findSubstring(s string, words []string) []int {
res := []int{} // 结果数组
wordNum := len(words)
if wordNum == 0 {
return res
}
wordLen := len(words[0]) // 每个单词的长度
allWords := make(map[string]int) // 存储所有单词及其出现次数
// 统计 words 中每个单词的出现次数
for _, w := range words {
allWords[w]++
}
// 将所有移动分成 wordLen 类情况
for j := 0; j < wordLen; j++ {
hasWords := make(map[string]int) // 记录当前窗口内单词出现次数
num := 0 // 当前窗口中有效单词的数量
// 每次移动一个单词长度
for i := j; i <= len(s)-wordNum*wordLen; i += wordLen {
hasRemoved := false // 标记是否移除过单词
for num < wordNum {
word := s[i+num*wordLen : i+(num+1)*wordLen] // 当前单词
if _, exists := allWords[word]; exists { // 如果单词在 allWords 中
hasWords[word]++
// 如果出现次数超过预期
if hasWords[word] > allWords[word] {
hasRemoved = true
removeNum := 0
// 一直移除单词，直到次数符合
for hasWords[word] > allWords[word] {
firstWord := s[i+removeNum*wordLen : i+(removeNum+1)*wordLen]
hasWords[firstWord]--
removeNum++
}
num = num - removeNum + 1 // 更新 num
i = i + (removeNum-1)*wordLen // 更新 i
break
}
} else { // 如果遇到不匹配的单词
hasWords = make(map[string]int) // 清空当前窗口
i += num * wordLen // 移动到问题单词后
num = 0
break
}
num++
}
// 如果 num == wordNum，说明找到一个匹配的子串
if num == wordNum {
res = append(res, i)
}
// 移除第一个单词以进行下一次迭代
if num > 0 && !hasRemoved {
firstWord := s[i : i+wordLen]
hasWords[firstWord]--
num--
}
}
}
return res
}
|