151 翻转单词
func reverseWords(s string) string {
// 思考： 判断单词条件是从0或者空格开始到终或者空格结尾，最简单方式strings.split之后变成切片，然后反转就行了
// 考虑双指针，左指针指向单词首位，右指针指向单词末尾
var res []byte
var left, right int
for right < len(s) {
// 题设至少存在一个单词，所以此处 left < len(s) 条件可以去除
for left < len(s) && s[left] == ' '{ // 通过字符串索引得到的是byte类型，所以应该通过‘’进行对比
left++
right = left
}
// 找到首位非空字符，单词的开始
for right < len(s) && s[right] != ' '{ // 判断单词结尾
right++
}
// 插入单词中间插入空格 s[left:right] + ' '
// 此处易错点，字符串索引之后是byte类型 ，但是切片操作之后还是字符串类型，本质上是一个子字符串
if left == right {
// 此时相当于单字符 byte
break
}
char := s[left:right] + string(' ')
res = append([]byte{}, append([]byte(char), res...)...) // 将区间字符 单词 插入到结果集开头
left = right // 将left位置重置到下一个单词开头
}
return string(res[:len(res)-1]) // 去除最后一位的空格
}
// 优化的前插方法
word := s[left:right]
if len(res) > 0 {
res = append([]byte{' '}, res...) // 插入空格
}
res = append([]byte(word), res...)
// 时间，总共遍历次数n（一次只有一个指针移动，移动完成，另一个跳到当前位置） 空间 n res创建了长度为n的byte切片
28 字符串匹配
func strStr(haystack string, needle string) int {
// 先考虑双指针思路
if len(needle) > len(haystack) {
return -1
}
if haystack == needle {
return 0
}
for i := 0; i < len(haystack); i++ {
if len(haystack[i:]) < len(needle) { // 匹配到后几位就无需继续循环了
return -1
}
for j := 0; j < len(needle); j++ {
if haystack[i+j] != needle[j] {
break
}
if j == len(needle) - 1{ // 匹配到末尾了，结束
return i
}
}
}
return -1
}
// 暴力双循环办法，时间m*n 空间 1
KMP 算法中的前缀表逻辑
KMP（Knuth-Morris-Pratt）算法通过前缀表（或部分匹配表）来加速字符串匹配过程。其核心思想是利用已经匹配过的部分信息，避免重复匹配，从而提高效率。以下是为什么在发生冲突时要取冲突字符前一位索引对应的前缀表值（即 next 数组值）作为新索引进行匹配的数学逻辑解释：
基本概念
- 前缀表（next 数组）：对于模式串 ( P )，前缀表
next[i]表示模式串 ( P ) 中从位置 0 到位置 ( i ) 的子串的最长相同前缀和后缀的长度。 - 冲突：在匹配过程中，如果主串 ( T ) 中的字符 ( T[j] ) 与模式串 ( P[k] ) 不匹配，就发生了冲突。
逻辑推导
假设在匹配过程中，主串 ( T ) 和模式串 ( P ) 已经匹配到了位置 ( j ) 和 ( k )，即 ( T[j] ) 与 ( P[k] ) 发生了冲突。此时我们需要决定下一步如何继续匹配。
1. 已匹配部分的特点
在匹配过程中，我们已经知道 ( P[ 0 ... k-1] ) 与 ( T[ j-k ... j-1 ] ) 是匹配的。这意味着：
[ T[ j-k ... j-1] = P[0 ... k-1] ]
2. 冲突发生
当 ( T[j] != P[k] ) 时，发生冲突。此时我们需要利用前缀表来决定模式串 ( P ) 的下一个匹配位置。
3. 前缀表的作用
前缀表 next[k] 表示模式串 ( P ) 中从位置 0 到位置 ( k-1 ) 的子串的最长相同前缀和后缀的长度。记这个长度为 ( len )，即：
[ len = next[k] ]
这意味着：
[ P[0 ... len-1] = P[k-len ... k-1] ]
4. 跳过不必要的比较
由于 ( P[0 ... len-1] ) 与 ( P[k-len ... k-1] ) 是相同的，我们可以跳过这部分已经匹配的前缀，直接从位置 ( len ) 开始继续匹配。这就是为什么在发生冲突时，我们将模式串的索引更新为 next[k] 的原因。
数学逻辑
- 已匹配部分的前缀和后缀相同：在匹配过程中，我们已经匹配了 ( P[0 ... k-1] ) 和 ( T[j-k ... j-1] )，并且 ( P[0 ... len-1] = P[k-len ... k-1] )。
- 避免重复匹配：在发生冲突时，如果我们重新从 ( P[0] ) 开始匹配，会导致重复比较已经匹配过的子串。通过前缀表，我们可以直接跳到下一个可能的匹配位置，从而避免重复比较。
- 递归性质：前缀表的值本身也是通过递归计算得到的，因此在发生冲突时，使用前缀表的值作为新的索引可以保证我们跳过的部分是已经匹配的部分，从而保证匹配的正确性。
例子
假设模式串 ( P = \text{"aabaa"} ) 和主串 ( T = \text{"aabaacaabaa"} )，我们在 ( T ) 中找到一个不匹配的位置：
- 当前匹配到 ( T[j] ) 和 ( P[k] )，即 ( T[5] = \text{"c"} ) 和 ( P[4] = \text{"a"} ) 不匹配。
- 此时 ( k = 4 )，前缀表
next[4] = 2，表示 ( P[0 ... 1] ) 与 ( P[2 ... 3] ) 是相同的。 - 因此，我们可以跳过前面已经匹配的部分，直接从 ( P[2] ) 开始继续匹配。
通过这种方式，KMP 算法利用前缀表在匹配过程中高效地跳过不必要的比较，从而提高了匹配效率。
实现代码
func nextSlice(s string) []int{
// kmp算法计算前缀数组： 最长相等前后缀
// kmp 思路，匹配到冲突字符时候，取当前字符前一位索引的next数组值，作为字符索引然后再进行匹配
// 1, 初始化
var (
k int // 存储当前位最长相等前后缀
next []int // 前缀数组
)
next = make([]int, len(s))
for i := 1; i < len(s); i++ {
// 2， 处理字符不相等情况，如果不相等，那么取当前位置索引的前一位的next数组值作为索引进行下一步匹配
for k > 0 && s[i] != s[k] { // 对比
// 找索引前一位next数组值作为索引
k = next[k-1] // 取新的next值作为索引
}
// 3，判断相等情况
if s[i] == s[k] {
k++
}
// 4，保存next数组
// next存储的是最长相等前后缀
// next[i] = k 表示 s[0:k-1] == s[i-k+1:i]，即 s[0:k] 是 s[0:i] 的最长相等前后缀
// 所以说明k的位置就是代表了最长相等前后缀
next[i] = k
}
return next
}
时间n （不是n^2 原因是并不是完整的两层循环，对于每个字符最多被访问2次，前进或者回退，所以只是一层遍历） 空间n
func strStr(haystack string, needle string) int {
// 双指针优化 kmp算法（通过前缀表实现逐步缩小匹配范围的作用，达到在大批量匹配效率的优化）
// 初始化next数组
next := nextSlice(needle)
fmt.Println(next)
var i, j = 0, 0
for i < len(haystack) { // tmd一定要先处理不等在处理想等情况，不然每次j都会被重置为0，太痛苦了
// 考虑不相等情况
for j > 0 && haystack[i] != needle[j] {
j = next[j-1] // 更新为next数组前一位值作为新索引
}
// 考虑相等
if haystack[i] == needle[j] {
if j == len(needle) - 1 {
return i - j
}
j++
}
i++ // 如果j回退到0仍然不相等，那么就i往后移动一位继续与j匹配
}
return -1
}
时间 n + m 空间n
459 判断重复子串
//leetcode submit region begin(Prohibit modification and deletion)
func repeatedSubstringPattern(s string) bool {
// 思考 kmp算法
next := nextSlice(s)
// 分析如果能够被字串重复构成
// 最长相等前后缀所不包含的部分就是公共字串， 对于重复串而言最长相等前后缀一定是next(len-1)
// 如果公共字串能够被字符串长度整除，那么就说明是重复串
lenght := len(s)
if next[lenght - 1] > 0 && lenght % (lenght - next[lenght - 1]) == 0 {
return true
}
return false
}
func nextSlice(s string) []int {
var (
k int
next []int
)
// new
next = make([]int, len(s))
for i := 1 ; i < len(s) ; i++ {
// not equal
for k > 0 && s[i] != s[k] {
k = next[k-1]
}
// equal
if s[i] == s[k]{
k++
}
// update next, because s[0:k-1] == s[i-k+1: i]
next[i] = k
}
return next
}
时间m+n 空间n
func repeatedSubstringPattern(s string) bool {
// 思考 移动匹配法， 通过将s + s然后判断 news[1:len(news)-2] 范围内出现过s实现判断
// 为什么区间是 1到length-1 ，因为目的是判断区间中间是否出现过s，所以要去除两端端点，防止出现被第一个s或者加到的第二个s匹配
var news strings.Builder
news.WriteString(s)
news.WriteString(s)
s2 := news.String()
if strings.Contains(s2[1: len(s2) - 1], s) {
return true
}
return false
}