Java 面試題 找出字串中是否有重複的字串 find if string contains repeat continuous character sequence

在最近的面試作業的需求中要求找出字串中是否有連續出現的子字串。

光看文字說明不太清楚要得是什麼，請看以下規則。

• 輸入：aa，輸出：true（a重覆）
• 輸入：11，輸出：true（1重覆）
• 輸入：123123，輸出：true（123重覆）
• 輸入：12abab，輸出：true（ab重覆）
• 輸入：123ab23ab，輸出：true（23ab重覆）
• 輸入：1，輸出：false
• 輸入：aba，輸出：false
• 輸入：abcab，輸出：false
• 輸入：123a321，輸出：false
• 輸入：1a2a，輸出：false
• 輸入：12abcab，輸出：false

這問題我花了一整天才想出來（上班通勤偶爾想的時間 + 週末下午到晚上盯著螢幕想的時間），上網google看有沒有類似的也沒找到只好自己想。

想出來的結果如下，看到三個for迴圈就覺得不對勁，一定有更好的寫法，目前想到的是可以計算剩餘字串的長度是否超過前面的比較長度來減少比較次數。

public class Main {

    public boolean hasRepeatCharacterSequence(String str) {
        if (str == null) {
            return false;
        }
        char[] chars = str.toCharArray();

        int lastIndex = chars.length - 1;
        for (int i = 0; i < chars.length; i++) {
            if (i >= lastIndex) { // 最後一個字離開，避免後面的動作導致ArrayIndexOutOfBoundsException
                break;
            }

            char nextChar = chars[i + 1]; // 取得目前字元的下個字元
            label:
            for (int j = 0; j <= i; j++) {
                if (nextChar == chars[j]) { // 將下個字元與從第一個字元開始往後比較到目前的字元。如果下個字元與第j個字相同
                    // 從j開始到i的字都與i到i + (i - j)的字都相同代表有重複。(i - j)即為j到i的長度
                    for (int k = 0; k <= (i - j); k++) {
                        if (i + 1 + k > lastIndex) { // 超出範圍
                            continue label;
                        }
                        if (chars[j + k] != chars[i + 1 + k]) {
                            continue label;
                        }
                    }
                    return true;
                }
            }
        }
        return false;
    }
}

JUnit 測試。

public class MainTests {

    private final Main main = new Main();

    @Test
    public void test() {
        Assertions.assertAll(
                () -> Assertions.assertTrue(main.hasRepeatCharacterSequence("aa")),
                () -> Assertions.assertTrue(main.hasRepeatCharacterSequence("11")),
                () -> Assertions.assertTrue(main.hasRepeatCharacterSequence("123123")),
                () -> Assertions.assertTrue(main.hasRepeatCharacterSequence("12abab")),
                () -> Assertions.assertTrue(main.hasRepeatCharacterSequence("123ab23ab")),
                () -> Assertions.assertFalse(main.hasRepeatCharacterSequence(null)),
                () -> Assertions.assertFalse(main.hasRepeatCharacterSequence("1")),
                () -> Assertions.assertFalse(main.hasRepeatCharacterSequence("aba")),
                () -> Assertions.assertFalse(main.hasRepeatCharacterSequence("abcab")),
                () -> Assertions.assertFalse(main.hasRepeatCharacterSequence("123a321")),
                () -> Assertions.assertFalse(main.hasRepeatCharacterSequence("1a2a")),
                () -> Assertions.assertFalse(main.hasRepeatCharacterSequence("12abcab"))
        );
    }
}

如果是現場白板題現場我肯定想不出來，不過如果有刷leetcode的話應該可以。