关注Java领域相关技术 记录有趣的事情

LeetCode-459. 重复的子字符串

US-B.Ralph
US-B.Ralph
2020-08-24

问题地址

LeetCode每日一题/2020-08-24

LeetCode459. 重复的子字符串


问题描述

规则

给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。

示例1

输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。

示例2

输入: "aba"
输出: False

示例3

输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

解析

解题思路

采用群举子串+条件约束,这里的约束条件有:
1. 子串的长度<=字符串长度的/2;
2. 字符串长度可以整除子串长度;

复杂度分析

  1. 时间复杂度,O(n^2),n是字符串的长度,极端情况下(s的长度为质数且s由同一个字符组成),共需要遍历O(n/2)*O(n)

  2. 空间复杂度,O(n/2),子串长度最大为字符串长度的一半,另外需要若干变量。

定位问题

  1. 暴力破解;

数据操作分析

  1. 限定条件判断,筛选子字符串;
  2. 使用字符串匹配字符串;

编码实现

/**
 * LeetCode459
 */
public class LeetCode459_RrepeatedSubstringPattern {
    public boolean repeatedSubstringPattern(String s) {

        if (s == null || s.length() <= 1) return false;

        String subStr = "";

        //s为同一个字符组成且s的长度为质数时,需循环n/2次
        for (int i = s.length() / 2; i > 0; i--) {
            subStr = s.substring(0, i);
            if (s.length() % subStr.length() == 0)
                if (patternSubStr(s, subStr)) return true;
        }

        return false;
    }

    private boolean patternSubStr(String s, String subStr) {

        int subLen = subStr.length();
        int matchingNum = s.length() / subLen;
        String sSub = "";
        int start;
        int end;
        //s为同一个字符组成且s的长度为质数时,需循环n次
        for (int i = 1; i < matchingNum; i++) {
            start = i * subLen;
            end = start + subLen;
            sSub = s.substring(start, end);
            if (!sSub.equals(subStr)) return false;
        }

        return true;
    }
}

官方解法

枚举

思路:
  • 如果一个长度为 n 的字符串 s 可以由它的一个长度为 n^’ 的子串 s^’ 重复多次构成,那么:n 一定是 n^’ 的倍数;s^’ 一定是 s 的前缀;对于任意的 i∈[n^′,n),有 s[i] = s[i-n^’]。也就是说,s 中长度为 n^’ 的前缀就是 s^’ ,并且在这之后的每一个位置上的字符 s[i],都需要与它之前的第 n^’ 个字符 s[i-n^’] 相同。因此,我们可以从小到大枚举 n^’,并对字符串 s 进行遍历,进行上述的判断。注意到一个小优化是,因为子串至少需要重复一次,所以 n^’ 不会大于 n 的一半,我们只需要在 [1, \frac{n}{2}] 的范围内枚举 n^’ 即可。
复杂度分析:
  • 时间复杂度:O(n^2),其中 n 是字符串 s 的长度。枚举 i 的时间复杂度为 O(n),遍历 s 的时间复杂度为 O(n),相乘即为总时间复杂度。

  • 空间复杂度:O(1)

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i * 2 <= n; ++i) {
            if (n % i == 0) {
                boolean match = true;
                for (int j = i; j < n; ++j) {
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }
}

字符串匹配

思路与算法
  • 我们可以把字符串 s 写成下面的形式,总计 \frac{n}{n’}s^’ 。但我们如何在不枚举 n^’ 的情况下,判断 s 是否能写成上述的形式呢?

$$
s^’s^’…s^’s^’
$$

  • 如果我们移除字符串 s 的前 n^’ 个字符(即一个完整的 s^’),再将这些字符保持顺序添加到剩余字符串的末尾,那么得到的字符串仍然是 s。由于 1 \leq n^’ < n,那么如果将两个 s 连在一起,并移除第一个和最后一个字符,那么得到的字符串一定包含 s,即 s 是它的一个子串。
  • 因此我们可以考虑这种方法:我们将两个 s 连在一起,并移除第一个和最后一个字符。如果 s 是该字符串的子串,那么 s 就满足题目要求。
  • 注意到我们证明的是如果 s 满足题目要求,那么 s 有这样的性质,而我们使用的方法却是如果 s 有这样的性质,那么 ss 满足题目要求。因此,只证明了充分性是远远不够的,我们还需要证明必要性。
  • 题解区的很多题解都忽略了这一点,但它是非常重要的。
  • 证明需要使用一些同余运算的小技巧,可以见方法三之后的「正确性证明」部分。这里先假设我们已经完成了证明,这样就可以使用非常简短的代码完成本题。在下面的代码中,我们可以从位置 11 开始查询,并希望查询结果不为位置 nn,这与移除字符串的第一个和最后一个字符是等价的。
复杂度分析:

由于我们使用了语言自带的字符串查找函数,因此这里不深入分析其时空复杂度。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return (s + s).indexOf(s, 1) != s.length();
    }
}

KMP算法

思路:

在方法二中,我们使用了语言自带的字符串查找函数。同样我们也可以自己实现这个函数,例如使用比较经典的 KMP 算法。读者需要注意以下几点:
– KMP 算法虽然有着良好的理论时间复杂度上限,但大部分语言自带的字符串查找函数并不是用 KMP 算法实现的。这是因为在实现 API 时,我们需要在平均时间复杂度和最坏时间复杂度二者之间权衡。普通的暴力匹配算法以及优化的 BM 算法拥有比 KMP 算法更为优秀的平均时间复杂度;
– 学习 KMP 算法时,一定要理解其本质。如果放弃阅读晦涩难懂的材料(即使大部分讲解 KMP 算法的材料都包含大量的图,但图毕竟只能描述特殊而非一般情况)而是直接去阅读代码,是永远无法学会 KMP 算法的。读者甚至无法理解 KMP 算法关键代码中的任意一行。
– 由于本题就是在一个字符串中查询另一个字符串是否出现,可以直接套用 KMP 算法。因此这里对 KMP 算法本身不再赘述。读者可以自行查阅资料进行学习。这里留了三个思考题,读者可以在学习完毕后尝试回答这三个问题,检验自己的学习成果:
– 设查询串的的长度为 n,模式串的长度为 m,我们需要判断模式串是否为查询串的子串。那么使用 KMP 算法处理该问题时的时间复杂度是多少?在分析时间复杂度时使用了哪一种分析方法?
– 如果有多个查询串,平均长度为 n,数量为 k,那么总时间复杂度是多少?\
– 在 KMP 算法中,对于模式串,我们需要预处理出一个 {fail} 数组(有时也称为 \textit{next} 数组、\pi 数组等)。这个数组到底表示了什么?

复杂度分析:
  • 时间复杂度:O(n),其中 n 是字符串 s 的长度。

  • 空间复杂度:O(n)

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return kmp(s + s, s);
    }

    public boolean kmp(String query, String pattern) {
        int n = query.length();
        int m = pattern.length();
        int[] fail = new int[m];
        Arrays.fill(fail, -1);
        for (int i = 1; i < m; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
                j = fail[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) {
                fail[i] = j + 1;
            }
        }
        int match = -1;
        for (int i = 1; i < n - 1; ++i) {
            while (match != -1 && pattern.charAt(match + 1) != query.charAt(i)) {
                match = fail[match];
            }
            if (pattern.charAt(match + 1) == query.charAt(i)) {
                ++match;
                if (match == m - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}
正确性证明:
  • 一方面,如果长度为 s 的字符串 s 是字符串 t=s+s 的子串,并且 s 在 tt 中的起始位置不为 0n,那么 s 就满足题目的要求。证明过程如下:
    我们设 st 中的起始位置为 ii \in (0, n))。也就是说,t 中从位置 i 开始的 n 个连续的字符,恰好就是字符串 s。那么我们有:s[0:n−1]=t[i:n+i−1]
    由于 t 是由两个 s 拼接而成的,我们可以将 t[i:n+i-1] 分成位置 n-1 左侧和右侧两部分:

$$
\begin{cases}
s[0:n−i−1]=t[i:n−1] \\
s[n−i:n−1]=t[n:n+i−1]=t[0:i−1] \\
\end{cases}
$$

  • 每一部分都可以对应回 ss:

\begin{cases}
s[0:n−i−1]=s[i:n−1] \\
s[n−i:n−1]=s[0:i−1] \\
\end{cases}

  • 这说明,s 是一个「可旋转」的字符串:将 s 的前 i 个字符保持顺序,移动到 s 的末尾,得到的新字符串与 s 相同。也就是说,在模 n 的意义下,s[j]=s[j+i] 对于任意的 jj 恒成立。
  • 「在模 n 的意义下」可以理解为,所有的加法运算的结果都需要对 n 取模,使得结果保持在 [0, n) 中,这样加法就自带了「旋转」的效果。如果我们不断地连写这个等式:s[j] = s[j+i] = s[j+2i] = s[j+3i] = ⋯
  • 那么所有满足 j_0 = j + k \cdot i 的位置 j_0 都有 s[j] = s[j_0]jj_0 在模 i 的意义下等价。由于我们已经在模 n 的意义下讨论这个问题,因此 jj_0 在模 \mathrm{gcd}(n, i) 的意义下等价,其中 \mathrm{gcd}表示最大公约数。也就是说,字符串 s 中的两个位置如果在模 \mathrm{gcd}(n, i) 的意义下等价,那么它们对应的字符必然是相同的。
  • 由于 \mathrm{gcd}(n, i) 一定是 n 的约数,那么字符串 s 一定可以由其长度为 \mathrm{gcd}(n, i) 的前缀重复 \frac{n}{\mathrm{gcd}(n, i)} 次构成。
  • 另一方面,如果 s 满足题目的要求,那么 s 包含若干个「部分」,t=s+s 包含两倍数量的「部分」,因此 s 显然是 t 的子串,并且起始位置可以不为 0n:我们只需要选择 t 中第一个「部分」的起始位置即可。
  • 综上所述,我们证明了:长度为 n 的字符串 s 是字符串 t=s+s 的子串,并且 st 中的起始位置不为 0n,当且仅当 s 满足题目的要求。
思考题答案:
  • 设查询串的的长度为 n,模式串的长度为 m,我们需要判断模式串是否为查询串的子串。那么使用 KMP 算法处理该问题时的时间复杂度是多少?在分析时间复杂度时使用了哪一种分析方法?
    • 时间复杂度为 O(n+m)),用到了均摊分析(摊还分析)的方法。
    • 具体地,无论在预处理过程还是查询过程中,虽然匹配失败时,指针会不断地根据 \textit{fail} 数组向左回退,看似时间复杂度会很高。但考虑匹配成功时,指针会向右移动一个位置,这一部分对应的时间复杂度为 O(n+m)。又因为向左移动的次数不会超过向右移动的次数,因此总时间复杂度仍然为 O(n+m))。
  • 如果有多个查询串,平均长度为 n,数量为 k,那么总时间复杂度是多少?
    • 时间复杂度为 O(nk+m)。模式串只需要预处理一次。
  • 在 KMP 算法中,对于模式串,我们需要预处理出一个 \textit{fail} 数组(有时也称为 \textit{next} 数组、\pi 数组等)。这个数组到底表示了什么?
    • $\textit{fail}[i]$ 等于满足下述要求的 $x$ 的最大值:$s[0:i]$ 具有长度为 $x+1$ 的完全相同的前缀和后缀。这也是 KMP 算法最重要的一部分。

优化的KMP算法

思路:

如果读者能够看懂「正确性证明」和「思考题答案」这两部分,那么一定已经发现了方法三中的 KMP 算法有可以优化的地方。即:

  • 在「正确性证明」部分,如果我们设 i 为最小的起始位置,那么一定有 \mathrm{gcd}(n, i) = i,即 ni 的倍数。这说明字符串 s 是由长度为 i 的前缀重复\frac{n}{i} 次构成;
  • 由于 \textit{fail}[n-1] 表示 s 具有长度为 \textit{fail}[n-1]+1 的完全相同的(且最长的)前缀和后缀。那么对于满足题目要求的字符串,一定有 \textit{fail}[n-1] = n-i-1,即 i = n – \textit{fail}[n-1] – 1;
  • 对于不满足题目要求的字符串,n 一定不是 n – \textit{fail}[n-1] – 1 的倍数。
  • 上述所有的结论都可以很容易地使用反证法证出。
  • 因此,我们在预处理出 \textit{fail} 数组后,只需要判断 n 是否为 n – \textit{fail}[n-1] – 1 的倍数即可。
复杂度分析:
  • 时间复杂度:O(n),其中 n 是字符串 s 的长度。

  • 空间复杂度:O(n)

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return kmp(s);
    }

    public boolean kmp(String pattern) {
        int n = pattern.length();
        int[] fail = new int[n];
        Arrays.fill(fail, -1);
        for (int i = 1; i < n; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
                j = fail[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) {
                fail[i] = j + 1;
            }
        }
        return fail[n - 1] != -1 && n % (n - fail[n - 1] - 1) == 0;
    }
}
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注