未分類

Longest Common Prefix

Go, LeetCode, String

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為字串中的開頭，同樣要在其它字串找一樣且最長的話，直接從位置一個個對照確認，因為要的只是開頭一樣。

分享到