字符串

字符串

类型1：旋转字符串

无论是循环字符串还是整体反转，都要用到一个reverse函数来辅助实现。

类型2：字符串包含

• leetcode 76. Minimum Window Substring

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.size() == 0)
            return "";
        string res = s;
        string cur;
        unordered_map<char, int> s_count, t_count;
        for (int i = 0; i < t.size(); ++i)
            t_count[t[i]]++;
        int left = 0;
        for (int i = 0; i < s.size(); ++i) {
            s_count[s[i]]++;
            cur += s.substr(i,1);
            char lastLetter = '.';
            while(isCovered(s_count, t_count, lastLetter)) {
                res = res.size() > cur.size() ? cur : res;
                lastLetter = s[left];
                s_count[s[left++]]--;
                cur.erase(cur.begin());
            }
        }
        s_count.clear();
        for (int i = 0; i < res.size(); ++i)
            s_count[res[i]]++;
        if(isCovered(s_count, t_count, '.'))
            return  res;
        else
            return "";
    }

• leetcode 3. Longest Substring Without Repeating Characters
  通常使用map和双指针来实现。

类型3：字符串转整数

• leetcode 8. String to Integer (atoi)
  需要考虑很多边界情况，1）判断开头有没有空格；2）判断符号；3）判断有没有溢出；4）判断是不是数字

class Solution {
public:
    int myAtoi(string str) {
        int n = str.size();
        if( n == 0) return 0;
        while(str[0] == ' ') 
            str.erase(0,1);
        n = str.size();
        int flag = 1;
        if( str[0] == '+') 
        {
            str[0] = '0';
        }
        else if(str[0] == '-')
        {
            flag = -1;
            str[0] = '0';
        }
        int64_t sum = 0;
        for(int i = 0; i < n; i++)
        {
            if(str[i] >='0' && str[i] <= '9')
            {
                sum = sum*10 + (str[i]-'0');
                if(flag*sum > INT_MAX)
                    return INT_MAX;
                if(flag*sum < INT_MIN)
                    return INT_MIN;
            }
            else 
            { 
                break;
            }
        }
        return flag*sum;
    }
};

类型4：回文判断

• 最长回文串 5. Longest Palindromic Substring
  思路1：动态规划
  dp[i][j]代表从i到j的子串是否能够构成回文串

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n == 0) return "";
        int dp[n][n] = {0}; // [i,j]
        int len = 1;
        int left = 0, right = 0;
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < i; j ++)
            {
                dp[j][i] = s[i] == s[j] && (i - j < 2 || dp[j+1][i-1]);
                if(dp[j][i] && len < i - j + 1 )
                {
                    len = i - j + 1;
                    left = j;
                    right = i;
                }
                
            }
            dp[i][i] = 1;
        }
        return s.substr(left,  len);
        
    }
};

思路2：枚举可能的回文串的中心，分奇偶情况。

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() == 0)
            return "";
        string res;
        for (int i = 0; i < s.size(); ++i) {
            // i is center
            int left = i;
            int right = i;
            while (left >= 0 and right < s.size() and s[left] == s[right]) {
                res = res.size() < (right - left + 1) ? s.substr(left, right - left + 1) : res;
                --left;
                ++right;
            }
            // i and i+1 is center
            left = i;
            right = i + 1;
            while (left >= 0 and right < s.size() and s[left] == s[right]) {
                res = res.size() < (right - left + 1) ? s.substr(left, right - left + 1) : res;
                --left;
                ++right;
            }
        }
        return res;
    }
};

思路3：Manacher's Algorithm， 马拉车解法，可以把时间复杂度降到o(n)
讲解过程参考：https://blog.csdn.net/dyx404514/article/details/42061017

类型5: 字符串的全排列

用回溯法／迭代来实现