在最近的面試作業的需求中要求找出字串中是否有連續出現的子字串。
光看文字說明不太清楚要得是什麼,請看以下規則。
- 輸入: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的話應該可以。
4 則留言:
個人淺見 看起來是用 雙指針 滑動窗口來解
哈哈,我之前聽過念資工的同事跟我解釋過滑動視窗,但至今仍沒花時間去理解:p
LeetCode no.459
public class StringUtils {
public static boolean containsRepeatedString(String s) {
if (s == null || s.length() <= 1) {
return false;
}
int n = s.length();
StringBuilder currentSequence = new StringBuilder();
for (int i = 0; i < n; i++) {
currentSequence.append(s.charAt(i));
int len = currentSequence.length();
if (i + 1 < n && s.startsWith(currentSequence.toString(), i + 1)) {
return true;
}
if (len * 2 <= n) {
continue;
}
currentSequence.deleteCharAt(0);
}
return false;
}
public static void main(String[] args) {
String[] inputs = {"aa", "11", "123123", "12abab", "123ab23ab", "1", "aba", "abcab", "123a321", "1a2a", "12abcab"};
for (String input : inputs) {
System.out.println("Input: " + input + ", Output: " + containsRepeatedString(input));
}
}
}
hope this can help
張貼留言