1. 翻转字符串里的单词

151

题目：
给你一个字符串 s ，颠倒字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

输入：s = "  hello world  "
输出："world hello"

思路：移除多余字符（空格）——将整个字符串反转——再把每个单词反转

移除多余空格，C++用的双指针法（原地），Python创建新字符串。

笔记：
erase()操作时间复杂度为O(n)，字符串能不用辅助空间最好不用

C++：

class Solution {
public:
    // 反转字符串s: 范围左闭右开
    void reverse(string& s, int start, int end){
        for(int i = start, j = end - 1; i < j; i++, j--){
            swap(s[i], s[j]);
        }
    }

    // 去除多余空格: 双指针法
    void removeExtraSpaces(string& s){
        int slowIndex = 0, fastIndex = 0;
        // remove字符串开头的空格
        while(s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' '){
            fastIndex++;
        }
        // remove字符串中间的空格
        for(; fastIndex < s.size(); fastIndex++){
            if(fastIndex - 1 > 0 
            && s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' '){
                continue;
            }else{
                s[slowIndex++] = s[fastIndex];
            }
        }
        // 重新调整字符串大小
        // 如果字符串尾有空格，由于fastIndex去重是去的后面那个空格，会导致最后剩一个空格，
        // 用slowIndex判断一下
        if(slowIndex - 1 > 0 && s[slowIndex - 1] == ' '){
            s.resize(slowIndex - 1);
        }else{
            s.resize(slowIndex);
        }
    }

    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverse(s, 0, s.size());
        // 划分单词，分反转单词
        for(int i = 0; i < s.size(); i++){
            int j = i;
            while(j < s.size() && s[j] != ' ') j++;
            reverse(s, i, j);
            i = j;
        }
        return s;
    }
};

// 另一种空格去重的双指针法：去除所有空格再在相邻单词前添加一个空格
void removeExtraSpaces(string& s){
        int slow = 0;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] != ' '){    // i指到非空格就要处理
                if(slow != 0) s[slow++] = ' ';     // 在每个单词前添加一个空格(除第一个单词外)
                while(i < s.size() && s[i] != ' '){   // 整个单词往前移
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow);
    }

Python：

class Solution:
    # 去除多余空格
    def remove_spaces(self, s):
        n = len(s)
        left = 0
        right = n - 1
        # 去除字符串开头空格
        while left <= right and s[left] == ' ':
            left += 1

        # 去除字符串结尾空格
        while left <= right and s[right] == ' ':
            right -= 1

        # 去除字符串中间空格
        newS = []  # 创建一个新字符串
        while left <= right:
            # 指向非空格，添加
            if s[left] != ' ':
                newS.append(s[left])
            # 指向空格，但新字符串中之前添加的不是空格，也可添加
            elif newS[-1] != ' ':
                newS.append(s[left])
            left += 1
        return newS

    # 反转整个字符串(左闭右闭)
    def reverse_string(self, s, left, right):
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
        return None

    # 反转每个单词(划分单词，再把每个单词看做一个字符串调用前面的)
    def reverse_each_word(self, s):
        i = 0
        j = 0
        while i < len(s):
            while j < len(s) and s[j] != ' ':
                j += 1
            self.reverse_string(s, i, j - 1)
            i = j + 1
            j += 1
        return None

    # 总
    def reverseWords(self, s: str) -> str:
        new_s = self.remove_spaces(s)
        self.reverse_string(new_s, 0, len(new_s) - 1)
        self.reverse_each_word(new_s)
        return ''.join(new_s)

2. 左旋转字符串

剑指Offer58-II

题目：
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

思路：若要不申请额外空间，就先局部反转，再整体反转
（反转前k个字符——反转后len() - k个字符——整体反转）

笔记：
python中

reverse()对象是list,无返回值,s.reverse()
reversed()对象是序列,这个序列可以是 tuple, string, list 或 range,返回值是一个反转后的迭代器

C++：

class Solution {
public:
    string reverseLeftWords(string s, int k) {
        reverse(s.begin(), s.begin() + k);
        reverse(s.begin() + k, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

Python：

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        s = list(s)
        s[0:n] = list(reversed(s[0:n]))
        s[n:] = list(reversed(s[n:]))
        s.reverse()

        return "".join(s)

3. 实现 strStr()

28

题目：
实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

输入：haystack = "hello", needle = "ll"
输出：2

思路：考察KMP经典算法

笔记：
KMP主要思想：当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。（前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。）

难点在找最长公共前后缀，前缀表：

构造Next数组

分三步：初始化——前后缀不相等情况——前后缀相等情况——更新next数组

首先，初始化：
j用于回退，j表示i之前包括i字串最长相等前后缀的长度。
即next[i] = j

i在j后面，不停前进。

使用Next数组做匹配

KMP模式串t匹配文本串s的操作类似于构造next数组。只是多加了一个判断条件：当j指向了模式串t的末尾时，表示文本串s中出现了模式串t。

定义j指向模式串起始位置，i指向文本串起始位置。

然后比较相等和不相等的情况同next数组，只是将s[i] s[j] 换成比较 s[i] t[j]。

C++：

class Solution {
public:
    void getNext(int* next, const string& s){
    // 初始化
    int j = 0;
    next[0] = j;

    for(int i = 1; i < s.size(); i++){
        // 前后缀不等
        while(j > 0 && s[j] != s[i]){
            j = next[j - 1]; // 回退位置为j前一位的next数组值
        }

        // 前后缀相等
        if(s[j] == s[i]){
            j++;
        }

        // 更新
        next[i] = j;
    }
}

    // haystack是文本串，needle是模式串
    int strStr(string haystack, string needle) {
        if(needle.size() == 0){
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = 0;
        for(int i = 0; i < haystack.size(); i++){
            // 不等
            while(j > 0 && haystack[i] != needle[j]){
                j = next[j-1];
            }
            // 相等
            if(haystack[i] == needle[j]){
                j++;
            }
            if(j == needle.size()){   // 因为此时j已经提前移动到下一位了，所以j实际指针已经超出模式串末尾指针
                return(i - needle.size() + 1);   // 而此时i还未i++，所以i还指在模式串最后一个字符相等处，是正常指针，所以要return(i - (needle.size() - 1))
            }
        }
        return -1;
    }
};

Python：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        a = len(needle)
        b = len(haystack)
        if a == 0:
            return 0
        next = self.getnext(a, needle)
        j = 0
        for i in range(0, len(haystack)):
            while (j > 0 and needle[j] != haystack[i]):
                j = next[j-1]
            if needle[j] == haystack[i]:
                j += 1
            if j == a:
                return i - a + 1
        return -1

    def getnext(self, a, needle):
        next = ['' for k in range(a)]
        j = 0
        next[0] = j
        for i in range(1, len(needle)):
            while (j>0 and needle[j] != needle[i]):
                j = next[j-1]
            if needle[j] == needle[i]:
                j += 1
            next[i] = j
        return next

4. 重复的子字符串

题目：给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

输入: s = "aba"
输出: false

思路：双倍字符串法，新字符串s+s中掐头去尾后，s仍在其中，则s是由多个子串重复构成的。

笔记：
Python:

C++：
find(s, 1) 表示在s+s中从下标开始找s字符串，返回匹配的第一个下标。若s中没有重复子字符串，只能找到第二个s，返回的刚好是s.size()。

反之，返回值将小于s.size()。

C++：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s + s).find(s, 1) != s.size();
    }
};

Python：

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return True if s in (s + s)[1:-1] else False