每天进步一点点🤏

重复的子字符串

  • ~2.69K 字

重复的子字符串

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成

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

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

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

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
思路:
具体思路看代码

代码:
/**
 * @param String $s
 *
 * @return Boolean
 */
function repeatedSubstringPattern($s)
{
    $count = strlen($s);
    //创建一个使用-1填充的长度和s一样的数组
    $indexMap = array_fill(0, $count, -1);

    // 下标i一直前进
    // 下标j根据能否匹配下标i当前的值前进或者回退
    for ($i = 1; $i < $count; $i++) {
        //上一次循环记录的j的下标
        $j = $indexMap[$i - 1];

        //如果j=-1,证明上个循环没有匹配到对应的值
        //如果j!=-1,s[i]!=s[j],证明出现了不匹配的情况,j需要回退到之前匹配的下标
        while ($j != -1 && $s[$i] !== $s[$j + 1]) {
            //j = j之前匹配的下标,为-1就从头开始
            $j = $indexMap[$j]; //如果依旧不匹配,回到更早的位置直到j=-1回到开头
        }

        if ($s[$i] == $s[$j + 1]) {
            //值匹配,i和j一起前进,j+1
            $indexMap[$i] = $j + 1;
        }
    }

    // 数组尾部为-1,证明尾部匹配失败,返回false
    // 数组尾部不为-1,存储的是匹配的下标,匹配的数量+1,总数-匹配的数量=重复的字符串长度,能被总数整除
    return $indexMap[$count - 1] !== -1 && $count % ($count - ($indexMap[$count - 1] + 1)) === 0;
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
思路:
将字符串前端的一部分移动到最后,拼接成一个新的字符串,如果新旧字符串相同,返回true

代码:
/**
 * @param String $s
 *
 * @return Boolean
 */
function repeatedSubstringPattern($s)
{
    $count = strlen($s);
    $mid   = intdiv($count, 2);
    for ($i = 1; $i <= $mid; $i++) {
        // 截取字符的前一段合并到后一段
        $newStr = substr($s, $i, $count - $i) . substr($s, 0, $i);

        if ($s === $newStr) {
            return true;
        }
    }

    return false;
}

解法3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
思路:
暴力枚举,同样是两个下标ij,当下标不匹配是,j的下标回到开头位置,i的下标回到上一个匹配的位置

代码:
/**
 * @param String $s
 *
 * @return Boolean
 */
function repeatedSubstringPattern($s)
{
    $count = strlen($s);
    //创建一个使用-1填充的长度和s一样的数组
    $indexMap = array_fill(0, $count, -1);

    $j    = 0;
    $last = 0;
    for ($i = 1; $i < $count; $i++) {
        if ($s[$j] === $s[$i]) {
            $indexMap[$i] = $j;
            if ($j === 0) {
                // 记录上一次开始匹配的位置
                $last = $i;
            }

            $j++;
        } else {
            // 不匹配,重制j的下标
            $j = 0;

            if ($last > 0) {
                // 如果已存在匹配的位置,i的下标回退到该位置
                $i    = $last;
                $last = 0;
            }
        }
    }

    return $indexMap[$count - 1] !== -1 && $count % ($count - ($indexMap[$count - 1] + 1)) === 0;
}