跳至主要內容

459, 重复的子字符串

Mike大约 2 分钟stringeasystringstring matching

一、题目描述

给定一个非空的字符串s,检查是否可以通过由它的一个子串重复多次构成。

示例 1
输入: s = "abab"
输出: true
解释: 可由子串"ab"重复两次构成。

示例 2
输入: s = "aba"
输出: false

示例 3
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串"abc"重复四次构成。(或子串"abcabc"重复两次构成。)

提示

  • 1 <= s.length <= 10⁴
  • s由小写英文字母组成

相关主题

  • 字符串
  • 字符串匹配

二、题解

方法 1: 暴力解法

/// Time Complexity: O(n^2)
///
/// Space Complexity: O(1)
pub fn repeated_substring_pattern(s: String) -> bool {
    let s = s.as_bytes();
    let len = s.len();

    for sub_len in 1..=len / 2 {
        if len % sub_len == 0 {
            let mut all_equal = true;
            for i in sub_len..len {
                if s[i] != s[i % sub_len] {
                    all_equal = false;
                    break;
                }
            }
            if all_equal {
                return true;
            }
        }
    }

    false
}

方法 2: KMP

/// Time Complexity: O(n)
///
/// Space Complexity: O(n)
pub fn repeated_substring_pattern(s: String) -> bool {
    let get_next = |needle: &[u8]| -> Vec<usize> {
        let m = needle.len();
        let mut next = vec![0; m];
        let mut j = 0;

        for i in 1..m {
            while j > 0 && needle[i] != needle[j] {
                j = next[j - 1];
            }
            if needle[i] == needle[j] {
                j += 1;
            }
            next[i] = j;
        }
        
        next
    };

    let needle = s.as_bytes();
    let next = get_next(needle);
    let len = needle.len();

    next[len - 1] != 0 && len % (len - next[len - 1]) == 0
}