乐趣区

关于后端:面试高频题难度-25笔试面试常客-字符串匹配问题的各种解法

题目形容

这是 LeetCode 上的 686. 反复叠加字符串匹配 ,难度为 中等

Tag :「字符串哈希」、「KMP」

给定两个字符串 ab,寻找反复叠加字符串 a 的最小次数,使得字符串 b 成为叠加后的字符串 a 的子串,如果不存在则返回 -1

留神:字符串 "abc" 反复叠加 0 次是 "",反复叠加 1 次是 "abc",反复叠加 2 次是 "abcabc"

示例 1:

输出:a = "abcd", b = "cdabcdab"

输入:3

解释:a 反复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。

示例 2:

输出:a = "a", b = "aa"

输入:2

示例 3:

输出:a = "a", b = "a"

输入:1

示例 4:

输出:a = "abc", b = "wxyz"

输入:-1

提醒:

  • $1 <= a.length <= 10^4$
  • $1 <= b.length <= 10^4$
  • ab 由小写英文字母组成

根本剖析

首先,能够剖析复制次数的「下界」和「上界」为何值:

对于「下界」的剖析是容易的:至多将 a 复制长度大于等于 b 的长度,才有可能匹配。

在明确了「下界」后,再剖析再通过多少次复制,可能明确失去答案,可能失去明确答案的最小复制次数即是上界。

因为主串是由 a 复制屡次而来,并且是从主串中找到子串 b,因而能够明确子串的起始地位,不会超过 a 的长度。

长度越过 a 长度的起始匹配地位,必然在此前曾经被匹配过了。

由此,咱们可知复制次数「上界」最多为「下界 + $1$」。

a 的长度为 $n$,b 的长度为 $m$,下界次数为 $c1$,上界次数为 $c2 = c1 + 1$。

因而咱们能够对 a 复制 $c2$ 次,失去主串后匹配 b,如果匹配胜利后的完结地位不超过了 $n * c1$,阐明复制 $c1$ 即可,返回 $c1$,超过则返回 $c2$;匹配不胜利则返回 $-1$。

卡常

这是我最开始的 AC 版本。

尽管这是道挺显然的子串匹配问题,然而昨晚比平时晚睡了一个多小时,早上起来精神状态不是很好,身材的每个细胞都在回绝写 KMP 🤣

就动了歪脑筋写了个「卡常」做法。

通过该做法再次印证了 LC 的评测机制非常奇葩:竟然不是对每个用例独自计时,也不是算总的用例用时,而是既算单用例耗时,又算总用时??

导致我间接 TLE 了 $6$ 次才通过(从 $700$ 试到了 $100$),其中有 $4$ 次 TLE 是显示通过了所有样例,但依然 TLE,我不了解为什么要设置这样蛊惑的机制。

回到该做法自身,首先对 a 进行复制确保长度大于等于 b,而后在肯定工夫内,一直的「复制 – 查看」,如果在规定工夫内可能找到则返回复制次数,否则返回 -1

代码:

import java.time.Clock;
class Solution {public int repeatedStringMatch(String a, String b) {StringBuilder sb = new StringBuilder();
        int ans = 0;
        while (sb.length() < b.length() && ++ans > 0) sb.append(a);
        Clock clock = Clock.systemDefaultZone();
        long start = clock.millis();
        while (clock.millis() - start < 100) {if (sb.indexOf(b) != -1) return ans;
            sb.append(a);
            ans++;
        }
        return -1;
    }
}
  • 工夫复杂度:$O(C)$
  • 空间复杂度:$O(C)$

上下界性质

通过「根本剖析」后,咱们发现「上下界」具备精确的大小关系,其实不须要用到「卡常」做法。

只须要进行「上界」次复制后,尝试匹配,依据匹配后果返回答案即可。

代码:

class Solution {public int repeatedStringMatch(String a, String b) {StringBuilder sb = new StringBuilder();
        int ans = 0;
        while (sb.length() < b.length() && ++ans > 0) sb.append(a);
        sb.append(a);
        int idx = sb.indexOf(b);
        if (idx == -1) return -1;
        return idx + b.length() > a.length() * ans ? ans + 1 : ans;
    }
}
  • 工夫复杂度:须要 $\left \lceil \frac{m}{n} \right \rceil + 1$ 次拷贝 和 一次子串匹配。复杂度为 $O(n * (\left \lceil \frac{m}{n} \right \rceil + 1))$
  • 空间复杂度:$O(n * (\left \lceil \frac{m}{n} \right \rceil + 1))$

KMP

其中 indexOf 局部能够通过 KMP/ 字符串哈希 实现,不相熟 KMP 的同学,能够查看 一文详解 KMP 算法,外面通过大量配图解说了 KMP 的匹配过程与提供了实用模板。

应用 KMP 代替 indexOf 能够无效利用主串是由多个 a 复制而来的性质。

代码:

class Solution {public int repeatedStringMatch(String a, String b) {StringBuilder sb = new StringBuilder();
        int ans = 0;
        while (sb.length() < b.length() && ++ans > 0) sb.append(a);
        sb.append(a);
        int idx = strStr(sb.toString(), b);
        if (idx == -1) return -1;
        return idx + b.length() > a.length() * ans ? ans + 1 : ans;
    }

    int strStr(String ss, String pp) {if (pp.isEmpty()) return 0;
        
        // 别离读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串后面都加空格,使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组,数组长度为匹配串的长度(next 数组是和匹配串相干的)int[] next = new int[m + 1];
        // 结构过程 i = 2,j = 0 开始,i 小于等于匹配串长度【结构 i 从 2 开始】for (int i = 2, j = 0; i <= m; i++) {// 匹配不胜利的话,j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配胜利的话,先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i],完结本次循环,i++
            next[i] = j;
        }

        // 匹配过程,i = 1,j = 0 开始,i 小于等于原串长度【匹配 i 从 1 开始】for (int i = 1, j = 0; i <= n; i++) {// 匹配不胜利 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配胜利的话,先让 j++,完结本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配胜利,间接返回下标
            if (j == m) return i - m;
        }
        return -1;
    }
}
  • 工夫复杂度:须要 $\left \lceil \frac{m}{n} \right \rceil + 1$ 次拷贝 和 一次子串匹配。复杂度为 $O(n * (\left \lceil \frac{m}{n} \right \rceil + 1))$
  • 空间复杂度:$O(n * (\left \lceil \frac{m}{n} \right \rceil + 1))$

字符串哈希

联合「根本剖析」,咱们晓得这实质是一个子串匹配问题,咱们能够应用「字符串哈希」来解决。

a 的长度为 $n$,b 的长度为 $m$。

依然是先将 a 复制「上界」次,失去主串 ss,目标是从 ss 中检测是否存在子串为 b

在字符串哈希中,为了不便,咱们将 ssb 进行拼接,设拼接后长度为 $len$,那么 b 串的哈希值为 $[len – m + 1, len]$ 局部(下标从 $1$ 开始),记为 $target$。

而后在 $[1, n]$ 范畴内枚举终点,尝试找长度为 $m$ 的哈希值与 $target$ 雷同的哈希值。

代码:

class Solution {public int repeatedStringMatch(String a, String b) {StringBuilder sb = new StringBuilder();
        int ans = 0;
        while (sb.length() < b.length() && ++ans > 0) sb.append(a);
        sb.append(a);
        int idx = strHash(sb.toString(), b);
        if (idx == -1) return -1;
        return idx + b.length() > a.length() * ans ? ans + 1 : ans;
    }
    int strHash(String ss, String b) {
        int P = 131;
        int n = ss.length(), m = b.length();
        String str = ss + b;
        int len = str.length();
        int[] h = new int[len + 10], p = new int[len + 10];
        h[0] = 0; p[0] = 1;
        for (int i = 0; i < len; i++) {p[i + 1] = p[i] * P;
            h[i + 1] = h[i] * P + str.charAt(i);
        }
        int r = len, l = r - m + 1;
        int target = h[r] - h[l - 1] * p[r - l + 1]; // b 的哈希值
        for (int i = 1; i <= n; i++) {
            int j = i + m - 1;
            int cur = h[j] - h[i - 1] * p[j - i + 1]; // 子串哈希值
            if (cur == target) return i - 1;
        }
        return -1;
    }
}
  • 工夫复杂度:须要 $\left \lceil \frac{m}{n} \right \rceil + 1$ 次拷贝 和 一次子串匹配。复杂度为 $O(n * (\left \lceil \frac{m}{n} \right \rceil + 1))$
  • 空间复杂度:$O(n * (\left \lceil \frac{m}{n} \right \rceil + 1))$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.686 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版