成品短视频网站源码搭建免费,九狐建设网站,建设网站优化,wordpress分类目录发不了文章文章目录 一、题目二、C# 题解 一、题目 字符串轮转。给定两个字符串 s1 和 s2#xff0c;请编写代码检查 s2 是否为 s1 旋转而成#xff08;比如#xff0c;waterbottle 是 erbottlewat 旋转后的字符串#xff09;。 点击此处跳转题目。
示例1: 输入#xff1a;s1 “wa… 文章目录 一、题目二、C# 题解 一、题目 字符串轮转。给定两个字符串 s1 和 s2请编写代码检查 s2 是否为 s1 旋转而成比如waterbottle 是 erbottlewat 旋转后的字符串。 点击此处跳转题目。
示例1: 输入s1 “waterbottle”, s2 “erbottlewat” 输出True 示例2: 输入s1 “aa”, s2 “aba” 输出False 提示
字符串长度在[0, 100000]范围内。
说明:
你能只调用一次检查子串的方法吗
二、C# 题解 可以将题目理解为从字符串内部切一刀换序重组判断是否能变为原字符串。但按照该思路写复杂度为 O ( n 2 ) O(n^2) O(n2)不是很理想因此还是从字符入手。 使用双指针 i,j 从左向右分别指向 s1,s2。i 的任务是遍历 s1查找 s2 在 s1 中的前缀j 的任务是标识 s2 中前缀的位置即 s2[0]~s2[j - 1] 为 s2 与 s1 相同的部分。 以 s1bunana, s2nabuna 为例可以看出s1buna | nas2na | bunas1 的后缀和 s2 的前缀想同均为 na算法的具体流程如下 b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ ⇓ b u n a n a ( s 1 ) i : ↑ n a b u n a ( s 2 ) j : ↑ \begin{array}{l} b u n a n a (s1)\\ i: \uparrow \\ n a b u n a (s2)\\ j: \uparrow \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} b u n a n a (s1)\\ i: \uparrow \\ n a b u n a (s2)\\ j: \uparrow \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} b u n a n a (s1)\\ i: \uparrow \\ n a b u n a (s2)\\ j: \uparrow \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} b u n a n a (s1)\\ i: \uparrow \\ n a b u n a (s2)\\ j: \uparrow \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} b u n a n a (s1)\\ i: \uparrow \\ n a b u n a (s2)\\ j: \uparrow \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} b u n a n a (s1)\\ i: \uparrow \\ n a b u n a (s2)\\ j: \uparrow \end{array}\\ ~\\\ \Downarrow\\ ~\\\ \begin{array}{l} b u n a n a (s1)\\ i: \uparrow \\ n a b u n a (s2)\\ j: \uparrow \end{array}\\ i:j:b↑n↑uanbaunnaa(s1)(s2) ⇓ i:j:bn↑u↑anbaunnaa(s1)(s2) ⇓ i:j:bn↑uan↑baunnaa(s1)(s2) ⇓ i:j:bnua↑nba↑unnaa(s1)(s2) ⇓ i:j:bn↑uanbaun↑naa(s1)(s2) ⇓ i:j:bnua↑nbaunna↑a(s1)(s2) ⇓ i:j:bnuanb↑aunnaa(s1)↑(s2) 最终i 指向 s1 的末尾j 指向 s2 前缀的后一字符即 s2 后缀的起始位置。
public class Solution {public bool IsFlipedString(string s1, string s2) {int l1 s1.Length, l2 s2.Length;if (l1 ! l2) return false; // 长度不相等直接否掉int i 0, j 0; // 双指针i 指 s1j 指 s2while (i l1) { // 遍历 s1寻找 s2 的前缀if (s1[i] s2[j]) j; // 如果字符相同则 j 后移else { // 字符不同则 i、j 回退i - j;j 0;}i; // i 始终前进}i 0;while (j l2) { // 检查 s2 后缀是否为 s1 前缀if (s1[i] ! s2[j]) return false;}return true;}
}时间复杂度一般情况下为 O ( n ) O(n) O(n)但波动较大。最坏情况为 O ( n 2 ) O(n^2) O(n2)即字符串包含大部分重复字符。可以使用 KMP 算法优化懒了没必要。空间复杂度 O ( 1 ) O(1) O(1)。
