代码随想录算法训练营第九天| 151.翻转字符串里的单词、卡码网55.右旋转字符串 、28. 找出字符串中第一个匹配项的下标、459. 重复的子字符串

Leetcode151.翻转字符串里的单词

题目链接：151. 反转字符串中的单词

C++：

class Solution {
public:
    void remove_blank(string &s){
        int slow = 0;
        for(int fast=0; fast < s.size(); fast++)
        {
            if(s[fast] != ' ')
            {
                if(slow > 0)
                    s[slow++] = ' ';
                while(fast < s.size() && s[fast] != ' ')
                    s[slow++] = s[fast++];
            }
        }
        s.resize(slow);
    }

    void reverse(int start, int end, string &s){
        while(start < end)
        {
            swap(s[start], s[end]);
            start++;
            end--;
        }
    }

    string reverseWords(string s) {
        //剔除空格
        remove_blank(s);
        //整体翻转字符串
        reverse(0, s.size()-1, s);
        //分单词翻转字符串
        int start = 0;
        for(int i=0; i <= s.size(); i++)
        {
            if(i == s.size() || s[i] == ' ')
            {
                int end = i - 1;
                reverse(start, end, s);
                start = i + 1;
            }
        }
        return s;
    }
};

Python：

class Solution:
    def reverseWords(self, s: str) -> str:
        result = s.split()
        left, right = 0, len(result)-1
        while(left < right):
            result[left], result[right] = result[right], result[left]
            left += 1
            right -= 1
        return ' '.join(result)

卡码网55.右旋转字符串 

题目链接：

C++：

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int main(void){
    int n;
    string s;
    cin >> n;
    cin >> s;
    
    reverse(s.begin(), s.end());
    reverse(s.begin(), s.begin()+n);
    reverse(s.begin()+n, s.end());
    
    cout << s << endl;
}

Python：

n = int(input())
s = input()

s = s[len(s)-n:] + s[:len(s)-n]
print(s)

Leetcode459. 重复的子字符串

题目链接：28. 找出字符串中第一个匹配项的下标

C++： 

class Solution {
public:
    int strStr(string haystack, string needle) {
        int l = haystack.size();
        int next[needle.size()];
        get_next(next, needle);
        int j = 0;
        for(int i = 0; i < l; i++)
        {
            while(j > 0 && haystack[i] != needle[j])
                j = next[j-1];
            if(haystack[i] == needle[j])
                j++;
            if(j == needle.size())
                return i-needle.size()+1;
        }
        return -1;
    }
    //找到next数组
    void get_next(int *next, const string &s)
    {
        next[0] = 0;
        int j = 0;
        for(int i = 1; i < s.size(); i++)
        {
            while(j > 0 && s[i] != s[j])
                j = next[j-1];
            if(s[i] == s[j])
                j++;
            next[i] = j;
        }
    }
};

Python：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # 找出next数组
        nxt = [0] * len(needle)
        j = 0
        for i in range(1, len(needle)):
            while j > 0 and needle[i] != needle[j]:
                j = nxt[j-1]
            if needle[i] == needle[j]:
                j += 1
            nxt[i] = j
        
        # 利用next数组查找重复字符
        m = 0
        for n in range(len(haystack)):
            while m > 0 and haystack[n] != needle[m]:
                m = nxt[m-1]
            if haystack[n] == needle[m]:
                m += 1
            if m == len(needle):
                return n-m+1
        return -1

Leetcode459. 重复的子字符串

题目链接：459. 重复的子字符串

C++：KMP

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        if(s.size() == 0)
            return false;
        //KMP
        int next[s.size()];
        get_next(next, s);
        if(next[s.size()-1] != 0 && (s.size() % (s.size() - next[s.size()-1])) == 0)
            return true;
        else
            return false;
    }

    void get_next(int* next, const string &str) {
        //初始化
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < str.size(); i++)
        {
            while(j > 0 && str[i] != str[j])
            {
                j = next[j-1];
            }
            if(str[i] == str[j])
                j++;
            next[i] = j;
        }
    }
};

Python：移动子串

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        # 移动子串
        ss = s + s
        return ss.find(s, 1, len(ss)-1) != -1