回傳最長的共同字首。
題目
Longest Common Prefix Easy
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.
我的解法
想法
計數器記錄幾個字都相同。
最後取出計算數量的的字做成字串回傳。
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
| class Solution {
public String longestCommonPrefix(String[] strs) {
int minLength = strs[0].length();
for (String str : strs) {
if (str.length() < minLength) {
minLength = str.length();
}
}
if (minLength == 0) {
return "";
}
boolean same = true;
int count = 0;
while (same && count < minLength) {
char c = strs[0].charAt(count);
for (String str : strs) {
if (str.charAt(count) != c) {
same = false;
}
}
if (same) {
count++;
}
}
if (count == 0) {
return "";
}
char[] ca = new char[count];
for (int i = 0; i < count; i++) {
ca[i] = strs[0].charAt(i);
}
return new String(ca);
}
}
|
注意
- String 長度會不同，要避免發生 StringIndexOutOfBoundsException。
檢討
我的方法算是從頭開始一個一個加，看到別人有用減法的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0) return "";
String pre = strs[0];
int i = 1;
while(i < strs.length){
while(strs[i].indexOf(pre) != 0)
pre = pre.substring(0, pre.length() - 1);
i++;
}
return pre;
}
}
|
重點物件或方法
String.indexOf()
String.substring()
參考資料
從LeetCode學演算法 - 2