Java 面試題：判斷字串中是否有連續重複字串

從菜鳥工程師 肉豬看到一個有意思的題目

要求是重複且連續，如
aa → true
ab → false
112 → true
121 → false
aa3aa3 → true
4abab5 → true

看他的答案之前先嘗試自己解答一下

思路

設計一個方法，傳入字串，返回布林

public boolean isDuplicate(String str) {
    return false;
}

既然是連續重複，可以直接拼接

if(str.contains(word + word)) {
    return true;
}

有多種排列組合，所以需要容器與迴圈

Set<String> words = new HashSet<String>();
for (String word : words) {

}

接下來決定 word 的範圍
6 個字只要判斷到 3 個字就可以了
因為會 * 2

int max = str.toCharArray().length / 2;

最後就是演算法
擷取一個字、兩個字、三個字…
這裡小心不要 ArrayIndexOutOfBoundsException

for (int i = 0; i < max; i++) {

    for (int j = 0; j < str.length() - i; j++) {

        int endIndex =  j + i + 1;
        words.add(str.substring(j, endIndex));
    }
}

還可以優化
如果是八個字的字串：12345678
第一遍（八個）：1、2、3、4、5、6、7、8
第二遍（七個）：12、23、34、45、56、67、78
第三遍（六個）：123、234、345、456、567、678
第四遍（五個）：1234、2345、3456、4567、5678

後續的比較是無意義的，應該改成
第一遍（七個）：1、2、3、4、5、6、7
第二遍（五個）：12、23、34、45、56
第三遍（三個）：123、234、345
第四遍（一個）：1234

int offset = i * 2 + 1;
for (int j = 0; j < str.length() - offset; j++) {

}

大功告成

public boolean isDuplicate(String str) {
    Set<String> words = new HashSet<String>();
    int max = str.toCharArray().length / 2;
		
    for (int i = 0; i < max; i++) {
        int offset = i * 2 + 1;
        for (int j = 0; j < str.length() - offset; j++) {
            int endIndex =  j + i + 1;
            words.add(str.substring(j, endIndex));
        }
    }
		
    for (String word : words) {
        if (str.contains(word + word)) {
            return true;
        }
    }
    return false;
}

測試

System.out.println(isDuplicate("aa")); //true
System.out.println(isDuplicate("ab")); //false
System.out.println(isDuplicate("112")); //true
System.out.println(isDuplicate("121")); //false
System.out.println(isDuplicate("aa3aa3")); //true
System.out.println(isDuplicate("4abab5")); //true
Tags: