題目描述：給定一個(gè)字符串s狸演，請計(jì)算輸出含有連續(xù)兩個(gè)s作為子串的最短字符串
思路：
- 從特殊到一般
abc -> abcabc，aba -> ababa僻他，aaa -> aaaa严沥，abcdab -> abcdabcdab - 論證確實(shí)是尋找包含s中最后一個(gè)字符的s的子串與包含s中第一個(gè)字符的s的子串相等的最長子串。
- 顯然result.length > s.length
- abcdab -> abcdabcd 不能是 abcdabcddc非最短字符串
- 證明
- 若result[0...r]為輸出的最短字符串中姜，
因r <= s.length時(shí)消玄，不可能出現(xiàn)兩個(gè)s作為子串跟伏，
則r > s.length。 - 其他證明略翩瓜，比較明顯受扳。
偽代碼：
java代碼
/**
* 題目：給定一個(gè)字符串s，請計(jì)算輸出含有連續(xù)兩個(gè)s作為子串的最短字符串
* e.g：1. 輸入abc兔跌，輸出abcabc 2. 輸入abcdab勘高，輸出abcdabcd，3. 輸入aaa坟桅，輸出aaaa
* @param s
* @return result
*/
private static char[] solution01(char[] s) {
int length = s.length;
// 記錄上一次迭代s(0...i-1)字符串頭尾有相同的字符串的字符個(gè)數(shù)
int dp = 0;
int i = 1;
while (i < length) {
if (s[dp] == s[i]) dp++;
else dp = 0;
i++;
}
if (dp == length - 1) {
// s = "a" 或者 s = "aaaa"
char[] result = new char[length + 1];
System.arraycopy(s, 0, result, 0, length);
result[length] = s[0];
return result;
} else {
char[] result = new char[2 * length - dp];
System.arraycopy(s, 0, result, 0, length);
System.arraycopy(s, dp, result, length, length - dp);
return result;
}
}
/**
* 只滿足s中只有26個(gè)英文字母
* @param s
* @return
*/
private static char[] solution02(char[] s) {
int length = s.length;
int i = 0, j = length - 1;
int head = 0, tail = 0, dp = 0;
while (i < length - 1) {
head = head * 26 + (s[i] - 'a' + 1);
tail = tail + (s[j] - 'a' + 1) * (int)Math.pow(26, i);
if (head == tail) {
dp = i + 1;
}
i++; j--;
}
if (dp == length - 1) {
// s = "a" 或者 s = "aaaa"
char[] result = new char[length + 1];
System.arraycopy(s, 0, result, 0, length);
result[length] = s[0];
return result;
} else {
char[] result = new char[2 * length - dp];
System.arraycopy(s, 0, result, 0, length);
System.arraycopy(s, dp, result, length, length - dp);
return result;
}
}
private static char[] solution03(char[] s) {
return new char[2];
}
public static void main(String[] args) {
System.out.println("----------solution01-------------");
// a
char[] s1 = "a".toCharArray();
System.out.println("輸入: " + String.valueOf(s1)
+ ", 輸出: " + String.valueOf(solution01(s1)));
// aaa
char[] s2 = "aaa".toCharArray();
System.out.println("輸入: " + String.valueOf(s2)
+ ", 輸出: " + String.valueOf(solution01(s2)));
// abc
char[] s3 = "abc".toCharArray();
System.out.println("輸入: " + String.valueOf(s3)
+ ", 輸出: " + String.valueOf(solution01(s3)));
// abcdabc
char[] s4 = "abcdabc".toCharArray();
System.out.println("輸入: " + String.valueOf(s4)
+ ", 輸出: " + String.valueOf(solution01(s4)));
System.out.println("----------solution02-------------");
// a
System.out.println("輸入: " + String.valueOf(s1)
+ ", 輸出: " + String.valueOf(solution02(s1)));
// aaa
System.out.println("輸入: " + String.valueOf(s2)
+ ", 輸出: " + String.valueOf(solution02(s2)));
// abc
System.out.println("輸入: " + String.valueOf(s3)
+ ", 輸出: " + String.valueOf(solution02(s3)));
// abcdabc
System.out.println("輸入: " + String.valueOf(s4)
+ ", 輸出: " + String.valueOf(solution02(s4)));
}
算法復(fù)雜度
solution01和solution02算法復(fù)雜度都是O(n)华望。
