题目描述

给定一个字符串s,请计算输出含有连续两个s作为子串的最短字符串

思路:

  1. 从特殊到一般
    abc -> abcabc,aba -> ababa,aaa -> aaaa,abcdab -> abcdabcdab
  2. 论证确实是寻找包含s中最后一个字符的s的子串与包含s中第一个字符的s的子串相等的最长子串。
  • 显然result.length > s.length
  • abcdab -> abcdabcd 不能是 abcdabcddc非最短字符串
  1. 证明
  • 若result[0…r]为输出的最短字符串,
    因r <= s.length时,不可能出现两个s作为子串,
    则r > s.length。
  • 其他证明略,比较明显。

答案

java代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/**
* 题目:给定一个字符串s,请计算输出含有连续两个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)字符串头尾有相同的字符串的字符个数
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个英文字母
* @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)));
}

算法复杂度

solution01和solution02算法复杂度都是O(n)。