代码训练营 Day9 | 151.翻转字符串里的单词 | 认识KMP算法

标签：151 word 前缀 Day9 后缀 fast next KMP string

151.翻转字符串里的单词

这道题的难度在于如何高效率的处理空格
对于python来说不能实现空间O(1)的复杂度，不过对于其他语言来说下面思路可以
1. 使用双指针方法同时指向数组的头部
2. 循环遍历整个字符串直到数组末尾
3. 快指针不能为空，因为快指针是要获取字母的，慢指针是用来获取新的字母存放位置的下标
4. 判断慢指针是否不为0，因为我们的单词可能在第一个单词前面也有空格，我们慢指针只是为了给翻转过后的单词间隔中间添加空格
5. 用while循环来不断删除多余的空格 (具体思路可以看Day1的帖子移除元素，只不过这里是移除空格思路不变)
整体思路
1. 使用reverse函数翻转整个字符串
2. 移除空格
3. 每个单独单词再次单独翻转

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str

        remove the empty space
        flip whole string
        flip the word
        """

        def remove_sapce(string):
            string = list(string)
            slow = 0    # get new array letter index
            fast = 0    # get letter

            # iterate the string
            while fast < len(string):
                # check if fast get number
                if string[fast] != " ":
                    # makesure it's not start of the word
                    if slow != 0:
                        # add space between each word
                        string[slow] = " "
                        slow += 1

                    # if there is extra space, or space for first word; remove it
                    while(fast < len(string) and string[fast] != " "):
                        # update the array remove space
                        string[slow] = string[fast]
                        # move both pointer
                        slow += 1
                        fast += 1
                fast += 1
                # return the new string, by using "".join to convert back to string, new index stop at slow

            return "".join(string[:slow])
        
        def reverse_string(string):
            # reverse the whole string
            return string[::-1]
        
        def reverse_word(string):
            # split the word between each space
            words = string.split(" ")
            
            # reverse each word
            return " ".join(word[::-1] for word in words)

        s = remove_sapce(s)
        s = reverse_string(s)
        s = reverse_word(s)

        return s

认识KMP

KMP与解决的问题

1. 文本串:aabaabaaf

2. 模式串:aabaaf

3. 求在文本串里是否出现过模式串

前缀表

1. 上述两个字符串在匹配的过程中当文本串的第二组aab遇到模式串aaf会发现b跟f不匹配了

2. 我们找到f的前面与其相等前缀(这里f的前缀是aa)的后面的那个字母也就是b，再重新开始匹配

前缀与后缀

1. 前缀: 包含首字母不包含为字母的所有子串都成为前缀

1. aabaaf: a aa aab aaba aabaa 都为前缀； aabaaf不是前缀因为包含了尾字母

2. 后缀: 只包含尾字母，不包含首字母成为后缀

1. aabaaf: f af aaf baaf abaaf 都为后缀； aabaaf不是后缀因为包含了首字母

最长相等前后缀

1. 字符相等前后缀

2. a 0

3. aa 1

4. aab 0

5. aaba 1

6. aabaa 2

7. aabaaf 0

上面 0 1 0 1 2 0 就是我们的前缀表

使用前缀表的匹配过程

1. 前缀表: 0 1 0 1 2 0

2. 我们前缀表最长相等前后缀的值就是我们重新开始匹配元素的下标

1. 我们跳到前缀的后面，前缀的后面它的下标就是前缀的长度，也就是最长相等前后缀的长度

2. 因为索引是从0开始所以这里我们跳到下标为2的地方也就是b

3. 从b这里重新开始匹配

Next数组

1. 遇到冲突的时候，next数组会告诉我们要回退到那里

2. 把前缀表做一个右移的操作；或者把前缀表整体减1的操作

3. 0 1 0 1 2 0 统一减1之后变成 -1 0 -1 0 1 -1

4. 拿这个这个前缀表去做匹配，统一减去1之后，还会把这个1加回来

缘分不动使用前缀表放入next数组依旧可以实现KMP算法；上面两种是不同形式

伪代码

### Next数组不同的实现方法 伪代码
遇到冲突的位置，我们要向前回退，这个是next数组的核心所在
```c++
// 文本串:aabaabaaf
// 模式串:aabaaf
// 前缀表:0 1 0 1 2 0；     看f前一位这个前缀表值是多少，这个值就对应下标值，我们应该跳到下标值的位置
// 往右移:-1 0 1 0 1 2      遇见冲突时候，直接比较f所对应的前缀表的值，跳到改值的下标位置
// 整体减1:-1 0 -1 0 1 -1   看f前一位，把之前减去的1加上来，再跳到该目标值
// 上面的方式实现方式都可以

// next是next数组，s是模式串
void getNext(next,s){
    //步骤一 初始化； 初始化函数里的变量和next数组
    int j = 0   //j:指向前缀位置; 还代表着i之前包括i字串最长相等前后缀的长度
    next[0] = 0 //next[0]=0,是因为当是只有一个字符的字符串，相同前后缀的最大长度是0
    //i:指向后缀位置; i从1开始这样才能和j进行比较
    for(i=1;i<s.size;i++){
        //步骤二 处理前后缀不相同的情况
        
        // j>0 如果j=0说明j已经回到初始位置； 切记使用while;因为回退不只是回退一次
        while (j > 0 && s[i] != s[j]){
            // 遇到冲突看前一位 前缀表值 并回头过去
            j = nums[j-1]
        }
        
        //步骤三 处理前后缀相同的情况
        if(s[i] == s[j]){
            j++ //还代表着i之前包括i字串最长相等前后缀的长度 由于相同所以需要++ 
        }
        //步骤四 更新next数组值
        next[i] = j;
    }    
}
```

标签：151,word,前缀,Day9,后缀,fast,next,KMP,string
From： https://blog.csdn.net/NeighborKing/article/details/141425054