算法日记 - 字符串六连

344. 反转字符串

344. 反转字符串 - 力扣（LeetCode）

class Solution {
public:
    void reverseString(vector<char>& s) {
        int lo = 0, hi = s.size() - 1, len = s.size();
        if (len < 2) return;
        while (lo <= hi)
        {
            char c = s[lo];
            s[lo] = s[hi];
            s[hi] = c;
            lo ++, hi--;
        }
    }
};

541. 反转字符串 II

541. 反转字符串 II - 力扣（LeetCode）

class Solution {
public:
    string reverseStr(string s, int k) {
        int pos = 0, len = s.size();
        if (len == 1) return s;
        while (pos < len)
        {
            // case 1 2k,反转前k个
            // case 2 k < len(剩余字符串) < 2k 反转前k个
            if (pos + k < len) reverse(s.begin() + pos, s.begin() + pos + k);
            // case 3 剩余少于k个 全反转
            else reverse(s.begin() + pos,s.end());
            pos += 2*k;
        }
        return s;
    }
};

LCR 122. 路径加密

LCR 122. 路径加密 - 力扣（LeetCode）

class Solution {
public:
    string pathEncryption(string path) {
        for (int i = 0; i < path.size(); ++i)
            if (path[i] == '.') path[i] = ' ';
        return path;
    }
};

LCR 182. 动态口令

LCR 182. 动态口令 - 力扣（LeetCode）

class Solution {
public:
    string dynamicPassword(string password, int target) {
        string res(password.begin() + target, password.end());
        // basic_string& append( const basic_string& str,size_type pos,size_type count );
        res.append(password,0,target);
        return res;
    }
};

28. 找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

class Solution {
public:
    //Partial Match Table
    void makePMT(const string& str,vector<int>& pmt)
    {
        for (int i = 1, j = 0; i < str.size(); ++ i)
        {
            while (j > 0 && str[i] != str[j]) j = pmt[j - 1];
            if (str[i] == str[j]) j ++;
            pmt[i] = j;
        }
    }
    // 移动位数 = 已匹配的字符数 - 对应的部分匹配值
    int strStr(string s, string p) {
        vector<int> pmt(p.size(), 0);
        makePMT(p,pmt);
        for (int i = 0, j = 0; i < s.size(); ++ i)
        {
            while (j > 0 && s[i] != p[j] ) j = pmt[j - 1];
            if (s[i] == p[j]) j ++;
            if (j == p.size()) return (i - j + 1);
        }
        return -1;
    }
};

459. 重复的子字符串

459. 重复的子字符串 - 力扣（LeetCode）

class Solution {
public:
    // 来自代码随想录，感谢carl
    void makePMT(const string& str,vector<int> &pmt)
    {
        for (int i = 1, j = 0; i < str.size(); i ++)
        {
            while (j > 0 && str[i] != str[j]) j = pmt[j - 1];
            if (str[i] == str[j]) j ++;
            pmt[i] = j; // 注意这里 --- 是[i]!@afjf#$!%#!g l 太容易写错了...
        }
    }
    bool repeatedSubstringPattern(string s) {
        int len = s.size();
        vector<int> pmt(s.size(), 0);
        makePMT(s,pmt);
        return (pmt[len - 1] != 0 && len % (len - pmt[len - 1]) == 0);
    }
};