最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

当前速递！【LeetCode字符串#extra】KMP巩固练习：旋转字符串、字符串轮转

来源：博客园

旋转字符串

https://leetcode.cn/problems/rotate-string/


(资料图)

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。

s 的 旋转操作 就是将 s 最左边的字符移动到最右边。

例如, 若 s = "abcde"，在旋转一次之后结果就是"bcdea" 。

示例 1:

输入: s = "abcde", goal = "cdeab"输出: true

示例 2:

输入: s = "abcde", goal = "abced"输出: false

提示:

1 <= s.length, goal.length <= 100s 和 goal 由小写英文字母组成

思路

与重复子串一样有两种思路：

1、直接将字符串s和goal相加，然后再相加后的字符串中查找s或者goal，找到就可以返回true

2、使用KMP算法

先求出s的next数组，然后还是将字符串s和goal相加，得到新字符串

将 goal字符串复制一份连接到自身末尾，得到新的字符串 s2的目的是为了模拟旋转操作之后的字符串。

假设原始字符串是 s，通过左旋若干次后得到的新字符串是 s"。如果我们将 s和 s"进行比较，就会发现它们实际上是相同的字符串，只是从不同位置开始截取的。而这个位置的关系可以通过将 goal复制一份连接到自身末尾来体现。

举个例子：假设 s = "abcde"，将 s左移两位得到的新字符串是 s" = "cdeab"。那么将 goal复制一份连接到自身末尾，得到的字符串是 goal + goal = "cdeababcde"。我们可以发现，在 goal + goal中，第一个 goal和 s"是对应的，因为它们都是从 c开始的；第二个 goal对应的就是 s，因为它们都是从 a开始的。

使用KMP算法在新字符串中查找s

为了这点醋包了这碗面

代码

字符串相加使用find
//与重复子字符串的简单版本思路类似class Solution {public:    bool rotateString(string s, string goal) {        return s.size() == goal.size() && (s + s).find(goal) != string::npos;    }};
脱裤子放屁法（KMP）
class Solution {private:    void getNext(int* next, string& s){        int j = -1;        next[0] = j;        for(int i = 1 ;i < s.size(); ++i){            while(j >= 0 && s[i] != s[j + 1]) j = next[j];            if(s[i] == s[j + 1]) j++;            next[i] = j;        }    }public:    bool rotateString(string s, string goal) {        //判断一下，如果两个字符串长度不等直接false，如果给的字符串是空，那怎么转都可以得到本身，返回true        //s为空goal不空的情况已经包含第一个判断中        if(s.size() != goal.size()) return false;        if(s.empty()) return true;        // 将goal字符串复制一份连接到自身末尾，得到新的字符串s2        string s2 = goal + goal; //string s2 = s + goal;也行        int j = -1;        int next[s.size()];        getNext(next, s);        for(int i = 0; i < s2.size(); ++i){//在s2中查找s            while(j >= 0 && s2[i] != s[j + 1]){                j = next[j];            }            if(s2[i] == s[j + 1]){                j++;            }            if(j == s.size() - 1) return true;//遍历完s后结束        }        return false;    }};

字符串轮转

https://leetcode.cn/problems/string-rotation-lcci/

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

示例1:

输入：s1 = "waterbottle", s2 = "erbottlewat"输出：True示例2:

输入：s1 = "aa", s2 = "aba"输出：False提示：

字符串长度在[0, 100000]范围内。说明:

你能只调用一次检查子串的方法吗？

思路

和旋转字符串一样，直接给代码

代码

字符串相加使用find
//与重复子字符串的简单版本思路类似class Solution {public:    bool isFlipedString(string s1, string s2) {        return s1.size() == s2.size() && (s2 + s2).find(s1) != string::npos;    }};
KMP
//kmp版本class Solution {private:    void getNext(int* next, string& s){        int j = -1;        next[0] = j;        for(int i = 1; i < s.size(); ++i){            while(j >= 0 && s[j + 1] != s[i]){                j = next[j];            }            if(s[j + 1] == s[i]) j++;            next[i] = j;        }    }public:    bool isFlipedString(string s1, string s2) {        if(s1.size() != s2.size()) return false;        if(s1.empty()) return true;        int j = -1;        int next[s1.size()];        string ss2 = s2 + s2;        getNext(next, s1);        for(int i = 0; i < ss2.size(); ++i){            while(j >= 0 && ss2[i] != s1[j + 1]) j = next[j];            if(ss2[i] == s1[j + 1]) j++;            if(j == s1.size() - 1) return true;        }        return false;    }};

关键词：