String_Leetcode

作者： /

844. Backspace String Compare

Solution 1 : # Stack

class Solution {
public:
    string build (string str){
        stack<char> st;
        for(auto c : str){
            if(c == '#'){
                if(!st.empty()){       
                    st.pop();          
                }
                else continue;    // specail case when '#' is at the beginning etc
            }                     // eg : '#f#g##', '####'
            else st.push(c);
        }
        string result = "";
        while(!st.empty()){
            result += st.top();
            st.pop();
        }
        return result;
    }
    bool backspaceCompare(string s, string t) {
        string newS = build(s);
        string newT = build(t);
        return newS == newT;
    }
};

Solution 2 : # Simulation

class Solution {
public:
    int validLength(string& str){     // simulation
        int k = 0;                    // k means the valid length of the string after remoing valid '#'
        for(auto c : str){
            if(c != '#'){
                str[k++] = c;
            }
            else if(k > 0) k--;     // valid '#' and erase one char
        }
        return k;
    }
    bool backspaceCompare(string s, string t) {
        int L1 = validLength(s);
        int L2 = validLength(t);
        if(L1 != L2) return false;
        for(int i = 0; i < L1; i++){      // special case like '###', '##'
            if(s[i] != t[i]) return false;
        }
        return true;       
    }
};

Minimum Window Substring

Solution: # Sliding window

class Solution {
public:
    string minWindow(string s, string t) {
        int m = s.size(), n = t.size();
        unordered_map<char, int> mp;
        for(auto c : t) mp[c]++;
        int ans = INT_MAX;
        int start = 0;
        int count = mp.size();   //需要匹配的种类数
        int i = 0, j = 0;
        while(j < m){
            mp[s[j]]--;
            if(mp[s[j]] == 0) count--;  // 如果s字符串里面某字符匹配上了,就减小count的字符种类数
            if(count == 0){          
                while(count == 0){
                    if(ans > j - i + 1){
                        ans = j - i + 1;
                        start = i;
                    }
                    mp[s[i]]++;      //尝试移动左边界,因此撤回一个匹配的字符，mp对应字符+1
                    if(mp[s[i]] > 0) count++; // 这种情况下需要匹配新的种类的字符
                    i++;              // 移动左边界
                }
            }
            j++;              // 移动右边界
        }
        return ans == INT_MAX ? "" : s.substr(start, ans);

    }

344. Reverse String

Solution 1: #Two pointers, 建立收尾两个指针然后向中间移动就好了

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i = 0, j = s.size() - 1; i < s.size() / 2; i++, j--){
            swap(s[i], s[j]);
        }
    }
};

Solution 2: #Recursion

class Solution {
public:
    void solve(vector<char>& s, int pos){
        if(pos >= s.size() / 2) return;
        swap(s[pos], s[s.size() - 1 - pos]);
        solve(s, ++pos);    // 这里不能用pos++,可以用++pos,或者pos+1
    }
    void reverseString(vector<char>& s) {
        solve(s, 0);
    }
};

541. Reverse String II

Solution 1: #Simulation, 就是特殊判断边界情况就好

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size(); i += 2 * k){
            if(i + k > s.size()) reverse(s.begin() + i, s.end());
            else reverse(s.begin() + i, s.begin() + i + k);
        }
        return s;
    }
};

Solution 2: 手搓一个reverse库函数

class Solution {
public:
    void s_reverse(string &s, int start, int end){
        for(int i = start, j = end; i < j; i++, j--) swap(s[i], s[j]);
    }
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size(); i += 2 * k){
            if(i + k > s.size()) s_reverse(s, i, s.size() - 1);   // attention !!!
            else s_reverse(s, i, i + k - 1);                      // the index should minus 1
        }
        return s;
    }
};

Solution 3: 用while循环♻️模拟

class Solution {
public:
    string reverseStr(string s, int k) {
        int pos = 0;
        while(pos < s.size()){
            if(pos + k > s.size()) reverse(s.begin() + pos, s.end());
            else reverse(s.begin() + pos, s.begin() + pos + k);
            pos += 2 * k;
        }
        return s;
    }
};

54. 替换数字（第八期模拟笔试）

Solution: #Two Pointers, 要从后往前填充

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    while(cin >> s){
        int old = s.size() - 1;
        int count = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] >= '0' && s[i] <= '9') count++;
        }
        s.resize(s.size() + count * 5);
        int NewIndex = s.size() - 1;
        while(old >= 0){
            if(s[old] >= '0' && s[old] <= '9'){
                s[NewIndex--] = 'r';
                s[NewIndex--] = 'e';
                s[NewIndex--] = 'b';
                s[NewIndex--] = 'm';
                s[NewIndex--] = 'u';
                s[NewIndex--] = 'n';
            }
            else{
                s[NewIndex--] = s[old];
            }
            old--;
        }
        cout << s << endl;
    }
    return 0;
}

151. Reverse Words in a String

Solution 1: #Two Pointers

class Solution {
public:
    string reverseWords(string s) {
        int slow = 0, fast = 0;
        bool wordStart = false;
        reverse(s.begin(), s.end());
        for(fast; fast < s.size(); fast++){
            if(s[fast] != ' '){
                if(wordStart && slow != 0) s[slow++] = ' '; // add blankspace
                int start = fast;
                while(fast < s.size() && s[fast] != ' '){
                    s[slow++] = s[fast++];
                }
                reverse(s.begin() + slow - (fast - start), s.begin() + slow);
                wordStart = true;   // new word starts
            }
        }
        s.resize(slow);    // resize the string
        return s;
    }
};

Solution 2: #Stack，用栈来模拟整个过程，简单易懂

class Solution {
public:
    string reverseWords(string s) {
        string result = "";
        stack<string> st;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == ' ') continue;
            string word = "";
            while(s[i] != ' ' && i < s.size()) word += s[i++];
            st.push(word);
        }
        while(!st.empty()){
            result += st.top();
            st.pop();
            if(!st.empty()) result += " ";   //不是最后一个单词的情况就要加空格
        }
        return result;
    }
};

55. 右旋字符串（第八期模拟笔试）

Solution 1: 不断翻转就行,因为不能开辟额外空间

#include<bits/stdc++.h>
using namespace std;
int main(){
    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;
    return 0;
}

Solution 2: 如果可以开辟额外空间的话，做法就是开子串

#include<bits/stdc++.h>
using namespace std;
int main(){
    int k; cin >> k;
    string s; cin >> s;
    string ss = s.substr(s.size() - k, k);
    s.erase(s.size() - k, k);
    ss += s;
    cout << ss << endl;
    return 0;
}

28. Find the Index of the First Occurrence in a String

Solution 1: 直接使用STL库函数

class Solution {
public:
    int strStr(string haystack, string needle) {
        size_t found = haystack.find(needle);
        if(found == string::npos) return -1;
        else return found;
    }
};

Solution 2: 直接手动模拟

class Solution {
public:
    int strStr(string haystack, string needle) {
        int left = 0, right = needle.size() - 1;
        while(right < haystack.size()){
            if(haystack[left] == needle[0] && haystack[right] == needle[needle.size() - 1]){
                int i = left, j = 0;
                while(i <= right && haystack[i++] == needle[j++]){
                    if(i == right + 1) return left;
                }
            }
            left++;
            right++;
        }
        return -1;
    }
};

Solution 3: # KMP, 不知道这里用KMP是不是自作多情了……但是也顺带复习一下吧

KMP最重要的是前缀表(prefix table)，前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。前缀表就是求最长相同前后缀的长度。KMP最重要的就是构建next数组。修考重点！！！！！经常回顾！
class Solution {
private:
    vector<int> next(string needle){     // 计算next数组
        int n = needle.size();
        vector<int> lps(n, 0);           //初始化公共前缀都为0
        for(int i = 1, len = 0; i < n;){
            if(needle[i] == needle[len]){
                lps[i++] = ++len;        // 当前字符匹配
            }
            else if(len){
                len = lps[len - 1]; // 如果不匹配且最长公共前后缀长度不为 0，回溯到前一个最长公共前后缀的位置
            }
            else{
                lps[i++] = 0; // 如果不匹配且最长公共前后缀长度为 0，说明当前字符无法匹配任何前后缀
            }
        }
        return lps;
    }
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        if(!n) return 0;   //// 如果 needle 为空字符串，直接返回 0
        vector<int> lps = next(needle);
        for(int i = 0, j = 0; i < m;){
            if(haystack[i] == needle[j]) i++, j++;   // // 如果当前字符匹配成功
            if(j == n) return i - j;     // // 如果 j 达到了 needle 的长度，说明完全匹配，返回起始位置
            if(i < m && haystack[i] != needle[j]){
                //// 如果当前字符不匹配，根据最长公共前后缀数组 lps 跳过部分已匹配的内容
                j ? j = lps[j - 1] : i++; // // 如果 j 不为 0，根据 lps 调整 j；否则，i 后移一位
            }
        }
        return -1;
    }
};

459. Repeated Substring Pattern

Solution 1: 把两倍的字符串拼接在一起然后掐头去尾再找是否有原字符串

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin());
        t.erase(t.end() - 1);
        if(t.find(s) == string::npos) return false;
        return true;
    }
};

Solution 2: # Brute force, 暴力找出重复子串

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string str = "";
        int pos = 0;
        while(pos < s.size() / 2){
            str += s[pos];
            string tmp = str;
            while(tmp.size() < s.size()) tmp += str;
            if(tmp == s) return true;
            pos++;
        }
        return false;
    }
};

409. Longest Palindrome

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> mp;
        for(char c : s) mp[c]++;
        int count = 0;
        bool hasOdd = false;
        for(auto &itr : mp){
            if(itr.second % 2 == 0){
                count += itr.second;
            }
            else{
                count += itr.second - 1;
                hasOdd = true;
            }
        }
        if(hasOdd) count += 1;
        return count;
    }
};
滚动至顶部