未分類

Longest Common Prefix

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

提示 解題應用
String Prefix String

Default:

1
2
3
func longestCommonPrefix(strs []string) string {
}

解答思路:

原本以為是要實作類似KMP這種字串比較來解答,結果題目不是找單一字串中前後綴最長的字串,而是更加單純,在字串陣列中找相同且最長的前綴字串,既然點出了前綴就表示要找相同的字串一定位置、順序在開頭都一模一樣,所以就一個一個位置檢查該字是否相同。

Example:

1
2
strs: ["ababa","aba","abc"]
return: "ab"

程式碼解說:

去掉題目所給預想狀況外的參數,像是空字串

1
2
3
if len(strs) == 0 {
return ""
}

剩餘的就相當單純的一字一字比較,先抽出第一個字串並以其一字一字與其它字串做比較,這邊比較要注意的是第一個字串有可能比其它字串來的長,要判斷index的值不能比其它字串長度長,然後只要發現字元不相同就可以跳出迴圈了,因為迴圈有兩層所以在外面的迴圈才加上了一個flag來判斷,最後把 index+1 拿到前綴的長度就可以知道結果了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var result int
first := strs[0]
flag := false
for index, s := range first {
for _, str := range strs[1:] {
if index < len(str) {
if string(s) != string(str[index]) {
flag = true
break
}
} else {
flag = true
break
}
}
if flag {
break
}
result = index + 1
}

完整程式碼:

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
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
var result int
first := strs[0]
flag := false
for index, s := range first {
for _, str := range strs[1:] {
if index < len(str) {
if string(s) != string(str[index]) {
flag = true
break
}
} else {
flag = true
break
}
}
if flag {
break
}
result = index + 1
}
return first[:result]
}

總結:

Prefix為字串中的開頭,同樣要在其它字串找一樣且最長的話,直接從位置一個個對照確認,因為要的只是開頭一樣。

分享到