C++刷题 -- 字符串

2023-12-20 23:47:32

C++刷题 – 字符串


1.重复的子字符串

https://leetcode.cn/problems/repeated-substring-pattern/submissions/490209402/
暴力解法
第一个for循环用来标定子串的末尾,根据末尾取出子串
第二个while循环用来检查原字符串是否由子串构成

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        for(int i = 0; i < s.size(); i++)
        {
            if(s.size() % (i + 1) != 0)
            {
                continue;
            }
            if(i >= s.size() / 2)
            {
                break;
            }
            string subStr = s.substr(0, i + 1);
            int length = i + 1;
            int pos = 0;
            while(pos < s.size())
            {
                if(subStr == s.substr(pos, length))
                {
                    pos += length;
                }
                else
                {
                    break;
                }
                if(pos == s.size())
                {
                    return true;
                }
            }
        }
        return false;
    }
};
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(1)

移动匹配
当一个字符串s:abcabc,内部由重复的子串组成,那么这个字符串的结构一定是这样的:
在这里插入图片描述
也就是由前后相同的子串组成。

那么既然前面有相同的子串,后面有相同的子串,用 s + s,这样组成的字符串中,后面的子串做前串,前面的子串做后串,就一定还能组成一个s,如图:
在这里插入图片描述
所以判断字符串s是否由重复子串组成,只要两个s拼接在一起,里面还出现一个s的话,就说明是由重复子串组成。

当然,我们在判断 s + s 拼接的字符串里是否出现一个s的的时候,要刨除 s + s 的首字符和尾字符,这样避免在s+s中搜索出原来的s,我们要搜索的是中间拼接出来的s。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
        if (t.find(s) != std::string::npos) return true; // r
        return false;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

不过这种算法最终还是要判断一个字符串中是由存在一个子串,该类库函数的实现可以使用KMP算法。

文章来源:https://blog.csdn.net/kissland96166/article/details/135118626
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。