免费注册个人网站,铁路工程造价信息网,wordpress em,网站见建设1 算法题 #xff1a;检查一个字符串是否是某个字符串的旋转
1.1 题目含义
检查一个字符串是否是某个字符串的旋转#xff0c;这是一个常见的字符串操作问题。具体来说#xff0c;这个问题要求判断给定的一个字符串是否可以通过将另一个字符串的所有字符按照相同的顺序进行…1 算法题 检查一个字符串是否是某个字符串的旋转
1.1 题目含义
检查一个字符串是否是某个字符串的旋转这是一个常见的字符串操作问题。具体来说这个问题要求判断给定的一个字符串是否可以通过将另一个字符串的所有字符按照相同的顺序进行循环位移即旋转来得到。
例如字符串 “abcde” 是 “cdeab” 的旋转因为可以将 “cdeab” 向左旋转两个位置得到 “abcde”。但是字符串 “abc” 并不是 “bcd” 的旋转因为即使尝试所有可能的旋转方式也无法得到 “abc”。
1.2 示例
示例 1
输入s1 “abcde”, s2 “cdeab”输出true解释字符串 “cdeab” 可以通过向左旋转两个位置得到字符串 “abcde”。
示例 2
输入s1 “abc”, s2 “bcd”输出false解释无法通过旋转字符串 “bcd” 来得到字符串 “abc”。
示例 3
输入s1 “waterbottle”, s2 “erbottlewat”输出true解释字符串 “erbottlewat” 可以通过向右旋转一定位置得到字符串 “waterbottle”。
2 解题思路
解题思路如下
1判断长度 首先检查两个字符串 s1 和 s2 的长度是否相等。如果长度不等那么 s2 显然不能是 s1 的旋转因为旋转操作不会改变字符串的长度。直接返回 false。
2拼接字符串 将 s1 和 s1 拼接在一起形成一个新的字符串 doubleS1。如果 s2 是 s1 的旋转那么 s2 必然是 doubleS1 的子串。
3查找子串 使用双指针在 doubleS1 中查找 s2。遍历 doubleS1每次检查从当前位置开始的子串是否与 s2 相等。这可以通过逐个字符比较来实现。
4返回结果 如果在 doubleS1 中找到了与 s2 相等的子串说明 s2 是 s1 的旋转返回 true。 如果遍历完整个 doubleS1 都没有找到匹配的子串则返回 false。
这个解题思路的时间复杂度是 O(n)其中 n 是字符串 s1或 s2的长度因为我们最多需要遍历 doubleS1 一次。空间复杂度是 O(n)因为需要存储拼接后的字符串 doubleS1。虽然这个空间复杂度不是最优的但这种方法实现起来比较简单并且对于大多数情况来说性能也是可接受的。如果需要进一步优化空间复杂度可以考虑不使用额外的空间存储拼接后的字符串但这通常会增加代码的复杂性。
3 算法实现代码
3.1 使用拼接遍历
如下为算法实现代码
#include iostream
#include string class Solution
{
public:bool isRotation(const std::string s1, const std::string s2){// 检查两个字符串长度是否相等 if (s1.length() ! s2.length()) {return false;}// 判断空字符串 if (s1.length() 0) {return true;}// 拼接字符串 std::string doubleS1 s1 s1;// 使用双指针查找子串 size_t s2Len s2.length();for (size_t i 0; i doubleS1.length() - s2Len 1; i) {if (doubleS1.substr(i, s2Len) s2) {// 找到匹配的子串返回true return true;}}// 没有找到匹配的子串返回false return false;}
};这段代码定义了一个 isRotation 函数它接受两个字符串 s1 和 s2 作为参数并返回一个布尔值表示 s2 是否是 s1 的旋转。
注意此代码使用了 std::string 类的 substr 成员函数来从 doubleS1 中提取与 s2 长度相同的子串并检查它们是否相等。这种方法简单直观但可能不是最高效的特别是当字符串很长时。在实际应用中可能需要根据性能要求进行优化。
调用上面的算法并得到输出
int main()
{Solution s;// 示例1 std::string s1 abcde;std::string s2 cdeab;std::cout Is s2 a rotation of s1 ? (s.isRotation(s1, s2) ? Yes : No) std::endl;// 示例2 s1 abc;s2 bcd;std::cout Is s2 a rotation of s1 ? (s.isRotation(s1, s2) ? Yes : No) std::endl;// 示例3 s1 waterbottle;s2 erbottlewat;std::cout Is s2 a rotation of s1 ? (s.isRotation(s1, s2) ? Yes : No) std::endl;return 0;
}上面代码的输出为
Is cdeab a rotation of abcde? Yes
Is bcd a rotation of abc? No
Is erbottlewat a rotation of waterbottle? Yes3.2 使用数组循环
上面算法的实现使用到了字符串拼接占用了一定的内存空间如果避免使用拼接字符串的方法可以将 s1 视为一个循环数组然后检查 s2 是否可以通过将 s1 的某个起始位置作为起点按照数组顺序读取得到。如果找到了这样的起始位置那么 s2 就是 s1 的旋转。
如下为算法实现代码
#include iostream
#include string
#include vector class Solution
{
public:bool isRotation(const std::string s1, const std::string s2){// 检查两个字符串长度是否相等 if (s1.length() ! s2.length()) {return false;}// 判断空字符串 if (s1.length() 0) {return true;}int n s1.size();for (int i 0; i n; i) {bool isMatch true;for (int j 0; j n; j) {int index (i j) % n; // 循环数组的索引 if (s1[index] ! s2[j]) {isMatch false;break;}}if (isMatch) {return true; // 找到匹配的起始位置 }}return false; // 没有找到匹配的起始位置 }
};在这个实现中使用了两个嵌套的循环。外部循环遍历 s1 的所有可能的起始位置内部循环则用于比较从当前起始位置开始的 s1 的子串和 s2 是否相同。内部循环使用取模运算 (i j) % n 来实现循环数组的索引这样就可以模拟从 s1 的不同位置开始读取字符的过程。
如果对于某个起始位置is1 的子串和 s2 完全相同那么就找到了匹配的起始位置并返回 true。如果遍历完所有可能的起始位置都没有找到匹配那么返回 false。
这种方法的时间复杂度是 O(n^2)其中 n 是字符串的长度因为代码中有两层循环。虽然这种方法避免了拼接字符串但它在处理长字符串时可能不够高效。对于更高效的解决方案可以考虑使用哈希表或其他数据结构来加速字符匹配的过程。
4 测试用例
以下是针对上面算法的测试用例基本覆盖了各种情况
1基础测试用例
输入1s1 “abcde”输入2s2 “cdeab”预期输出trues2 是 s1 的旋转因为 s1 可以通过将末尾的de移到开头得到 s2
2完全相同字符串
输入1s1 “abcde”输入2s2 “abcde”预期输出true相同的字符串可以视为自己的旋转
3长度不同字符串
输入1s1 “abcde”输入2s2 “abcdef”预期输出falses2 不是 s1 的旋转因为它们的长度不同
4旋转一个字符
输入1s1 “a”输入2s2 “a”预期输出true一个字符的旋转是其自身
5非旋转字符串
输入1s1 “hello”输入2s2 “olleh”预期输出falses2 不是 s1 的旋转因为即使移动 s1 的字符也无法得到 s2
6包含重复字符的字符串
输入1s1 “abbacaa”输入2s2 “bacaaab”预期输出true尽管 s1 和 s2 都包含重复字符但 s2 仍然是 s1 的旋转
7空字符串
输入1s1 “”输入2s2 “”预期输出true空字符串是自身的旋转
