未分類

Longest Palindromic Substring

Go, LeetCode, String

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
4
5
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
3
Input: "cbbd"
Output: "bb"
提示 解題應用
String 規律觀查

Default:

1
2
3
func longestPalindrome(s string) string {
}

解答思路:

這題總共分為兩種作法，一種是從最長的字串並慢慢縮減開始找，如下:

此方法主要是以長度為主開始找，若該長度沒有回文字串存在則將長度-1，miss就是拿來控制長度的參數，接著就是不斷的在字串上一邊位移，一邊確認此長度的字串是否為回文，如果為回文就直接回傳結果

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 longestPalindrome(s string) string {
	for miss := 0; miss < len(s); miss++ {
		for i := 0; i <= miss; i++ {
			if isPalidrome(s[i : i+len(s)-miss]) {
				return s[i : i+len(s)-miss]
			}
		}
	}
	return s
}
func isPalidrome(s string) bool {
	var strFront string
	var strRear string
	front := 0
	rear := len(s) - 1
	for front < rear {
		strFront = string(s[front])
		strRear = string(s[rear])
		if strFront != strRear {
			return false
		}
		front++
		rear--
	}
	return true
}

不過此方式在最後一個測資被刁專而導致超時，不過我認為這也是一種方式，原因在於若回文的字串都比較長的情況下這種方式反而比較適合，所以就端看碰上何種資料而採取何種辦法了

而另一種是從最短的字串並慢慢增加開始找，這也是這題最主要的解法，當然如果是從最短慢慢開始加那麼又會有兩種情況，因為回文有可能是完全對稱，或者是只有最中間一個任意值其餘才是兩兩對稱，所以說如果要一邊移動重置再一邊慢慢增加就還需要考慮到上述兩種情況，剩下的就只是檢查值是否對稱及index位置是否超出範圍等問題而已

程式碼解說:

一開始如果給予的字串為空或者只有一個字元就直接回傳整個字串，如果不是上述情況才開始遍歷整個字串，因為有完全對稱與最中間一個任意值其餘才是兩兩對稱的兩種情況，所以我們將前者稱為偶數的情況而後者則為奇數(已長度來區分)，因為慢慢增加字元是從左右兩邊同時增加，奇數的情況就從同一個位置往左右兩邊向外移動，偶數的情況則是從相鄰的兩個位置同時向外移動，如果奇數或偶數回傳的字串比結果大就取代，接著一邊移動重置再從頭慢慢增加，直到字串遍歷結束才回傳結果值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func longestPalindrome(s string) string {
	var odd string
	var even string
	var result string
	if len(s) <= 1 {
		return s
	}
	for i, _ := range s {
		odd = extendPalindrome(s, i, i)
		even = extendPalindrome(s, i, i+1)
		if len(odd) > len(result) {
			result = odd
		}
		if len(even) > len(result) {
			result = even
		}
	}
	return result
}

這部分則是左右向外增加字元並同時檢查是否回文，而如果是奇數的情況因為是從同一個位置出發，所以一開始左右位置的字元必定相同，接下來才與偶數的情況一樣，檢查左邊index是否大於0，右邊index是否超出字串長度，最後才是檢查左右兩邊的值是否相同，如果相同則左右兩邊繼續向外擴充以找到更長的回文，當左或右任一邊已經超出index的範圍而跳出回圈時，最後記得要將左右兩邊的index值同時縮一點回去才回傳結果

1
2
3
4
5
6
7
8
9
func extendPalindrome(s string, left int, right int) string {
	for left >= 0 && right < len(s) && s[left] == s[right] {
		left--
		right++
	}
	left++
	right--
	return s[left : right+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
27
28
func longestPalindrome(s string) string {
	var odd string
	var even string
	var result string
	if len(s) <= 1 {
		return s
	}
	for i, _ := range s {
		odd = extendPalindrome(s, i, i)
		even = extendPalindrome(s, i, i+1)
		if len(odd) > len(result) {
			result = odd
		}
		if len(even) > len(result) {
			result = even
		}
	}
	return result
}
func extendPalindrome(s string, left int, right int) string {
	for left >= 0 && right < len(s) && s[left] == s[right] {
		left--
		right++
	}
	left++
	right--
	return s[left : right+1]
}

總結:

要找出一字串中的子回文字串共有兩種方法，一種是從最長的字串並慢慢縮減開始找，一邊位移一邊確認此長度的字串是否為回文，而另一種則是從最短的字串並慢慢增加開始找，一邊移動重置再一邊慢慢增加且要注意有完全對稱與最中間一個任意值其餘才是兩兩對稱的兩種情況。

分享到