当前位置: 首页 > biancheng >正文

算法笔记-lc-面试题 01.09. 字符串轮转(中等)

算法笔记-lc-面试题 01.09. 字符串轮转(中等)

  • 题目
    • 题干
    • 示例
    • 提示:
    • 说明:
  • 题解
    • 方法一:模拟
    • 方法三:字符串哈希

题目

题干

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

示例

示例1:

输入:s1 = “waterbottle”, s2 = “erbottlewat”
输出:True
示例2:

输入:s1 = “aa”, s2 = “aba”
输出:False

提示:

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

说明:

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

题解

方法一:模拟

思路

首先,如果 s1和 s2的长度不一样,那么无论怎么轮转,s1都不能得到 s2 ,返回false。在长度一样(都为 n)的前提下,假设 s1轮转 i位,则与 s2中的某一位字符 s2[j] 对应的原 s1 中的字符应该为s1[(i+j)modn]。在固定 i 的情况下,遍历所有 j,若对应字符都相同,则返回true。否则,继续遍历其他候选的 i。若所有的 i 都不能使s1变成 s2
​ ,则返回 false。

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        if (m != n) {
            return false;
        }
        if (n == 0) {
            return true;
        }
        for (int i = 0; i < n; i++) {
            boolean flag = true;
            for (int j = 0; j < n; j++) {
                if (s1.charAt((i + j) % n) != s2.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return true;
            }
        }
        return false;
    }
}

复杂度分析

时间复杂度:O(n^2),其中 n 是字符串 s1的长度。我们需要双重循环来判断。

空间复杂度:O(1)。仅使用常数空间。

方法二:搜索子字符串
思路

首先,如果 s1和 s2的长度不一样,那么无论怎么轮转,s1都不能得到 s 2 ,返回 \text{false}false。字符串 s+s 包含了所有 s1 可以通过轮转操作得到的字符串,只需要检查 s2 是否为 s+s 的子字符串即可。

class Solution {
    public boolean isFlipedString(String s1, String s2) {
        return s1.length() == s2.length() && (s1 + s1).contains(s2);
    }
}

复杂度分析

时间复杂度:O(n),其中 n 是字符串 s1的长度。KMP 算法搜索子字符串的时间复杂度为O(n),其他搜索子字符串的方法会略有差异。

空间复杂度:O(n),其中 n 是字符串 s1 的长度。KMP 算法搜索子字符串的空间复杂度为 O(n),其他搜索子字符串的方法会略有差异。

方法三:字符串哈希

若两字符串互为旋转,则「其一字符串」必然为「另一字符串拓展两倍长度后(循环子串)」的子串。

基于此,我们可以使用「字符串哈希」进行求解:先计算 s2 的字符串哈希值 t,然后构造出 s1 + s1 的哈希数组和次方数组,在两数组中检查是否存在长度为 n 的连续子段的哈希值 cur 与 t 相等。

一些细节:其他语言可能不像 Java 那样存在自然取模,可手动取模,对于自带高精度的语言若不取模会导致单次计算复杂度上升,会 TLE。

class Solution {
    static int N = 200010, P = 13131;
    static int[] h = new int[N], p = new int[N];
    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int n = s1.length();
        for (int i = 1; i <= n; i++) h[i] = h[i - 1] * P + s2.charAt(i - 1);
        int t = h[n]; // s2 hash
        s1 = s1 + s1;
        p[0] = 1;
        for (int i = 1; i <= 2 * n; i++) {
            h[i] = h[i - 1] * P + s1.charAt(i - 1);
            p[i] = p[i - 1] * P;
        }
        for (int i = 1; i + n - 1 <= 2 * n; i++) {
            int j = i + n - 1, cur = h[j] - h[i - 1] * p[j - i + 1];
            if (cur == t) return true;
        }
        return false;
    }
}

时间复杂度:O(n)
空间复杂度:O(n)

相关文章:

  • switch循环语句
  • 牛客练习赛#84 F 莫比乌斯反演+杜教筛+技巧+斐波那契数列和gcd的结论+矩阵快速幂
  • ZZNUOJ_用C语言编写程序实现1342:支配值数目(附完整源码)
  • java毕业设计后勤管理系统餐饮评价监督系统(附源码、数据库)
  • 前端基础学习笔记
  • 【TS】联合类型--类型断言--类型推断
  • 谈笑风声的秘密
  • QT影城网上售票系统
  • NetCDF数据在ArcMap中的使用
  • 打怪升级(考验思路)