796.旋转字符串

链接：796.旋转字符串
难度：Easy
标签：字符串、字符串匹配
简介：给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。

题解 1 - cpp

• 编辑时间：2022-03-18
• 内存消耗：6.1MB
• 编程语言：cpp
• 解法介绍：找到所有下标起始点进行遍历。

class Solution {
   public:
    bool rotateString(string s, string goal) {
        if (s.size() != goal.size()) return false;
        vector<int> idxs = findidx(s, goal[0]);
        for (auto &idx : idxs) {
            if (check(s, goal, idx)) return true;
        }
        return false;
    }
    bool check(const string &s, const string &goal, const int &idx) {
        int i1 = idx, i2 = 0, n = s.size();
        while (i2 < n) {
            if (s[i1] != goal[i2]) return false;
            i1 = (i1 + 1) % s.size();
            i2++;
        }
        return true;
    }
    vector<int> findidx(const string &s, const char &ch) {
        vector<int> ans;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ch) ans.push_back(i);
        }
        return ans;
    }
};

题解 2 - cpp

• 编辑时间：2022-04-07
• 内存消耗：6MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
   public:
    int n;
    bool rotateString(string s, string goal) {
        n = s.size();
        vector<int> list;
        for (int i = 0; i < n; i++) {
            if (s[i] == goal[0]) list.push_back(i);
        }
        for (auto &start : list) {
            if (check(s, goal, start)) return true;
        }
        return false;
    }
    bool check(string &s, string &goal, int start) {
        for (int i = 0; i < n; i++, start = (start + 1) % n) {
            if (s[start] != goal[i]) return false;
        }
        return true;
    }
};