未分類

Palindrome Partitioning

Backtracking, Go, LeetCode

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example:

Given s = “aab”,
Return

1
2
3
4
[
  ["aa","b"],
  ["a","a","b"]
]
提示 解題應用
Backtracking Recursive

Default:

1
2
3
func partition(s string) [][]string {
}

解答思路:

這題卡了很長一段時間，原因在於最初覺得應該要透過規定好的長度來找出範圍內的回文，並再將該範圍慢慢擴大最後至整個字串，然而題目要的是字串拆開後所有各別的子字串也都是回文，這種做法很難透過簡單的遞回實現，整個過程會變的相當複雜，當看到其它人的討論才豁然開朗，甚至還有人用畫題圖來解說讓人一看便完全理解，整個流程其實非常簡單，如下:

charlie yupeng solution

其實就是從開頭開始慢慢增長子字串，每次檢查最前面增長的那一段字串是否符合回文，如果不符合就繼續增長再做檢查，而如果符合則將後面其餘的子字串做遞回並重覆上述動作，直到最後剛開始開頭增長的子字串已經到達與原字串相同長度並列出所有符合回文條件的子字串組合。

程式碼解說:

因為是透過遞回來列出所有符合回文條件的子字串組合，所以一開始就將字串帶入遞回函數之中，其中第二個參數是目前已符合回文條件的子字串

1
2
3
func partition(s string) [][]string {
	return backTrack(s, []string{})
}

接下來就是處理遞回函數的細節，如果進來的字串為空就直接回傳目前已符合回文條件的子字串，因為slice的特性所以這邊會需要將其複製一份再做回傳，而如果還有字串存在正如思路所述，從開頭開始慢慢增長子字串，每次檢查最前面增長的那一段字串是否符合回文，如果不符合就繼續增長再做檢查，符合的話則將後面其餘的子字串做遞回以重覆上述動作，並記得將最前面符合回文條件的增長字串放入子字串組合中再跟著帶入遞回，直到找出所有符合回文條件的子字串組合才向上回傳整個結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func backTrack(s string, set []string) [][]string {
	if len(s) == 0 {
		tmpSet := make([]string, len(set))
		copy(tmpSet, set)
		return [][]string{tmpSet}
	}
	var subString string
	var tmp [][]string
	var result [][]string
	for i, _ := range s {
		subString = s[:i+1]
		if !isPalindrome(subString) {
			continue
		}
		tmp = backTrack(s[i+1:], append(set, subString))
		result = append(result, tmp...)
	}
	return result
}

最後這部分的程式碼就只是用兩個指標分別指向字串的頭與尾，並逐漸向內縮檢查頭與尾所指向的字元兩邊是否相同，如果不同就回傳false直到兩個指標都指向同一個字元才停止迴圈並回傳true

1
2
3
4
5
6
7
8
9
10
11
12
func isPalindrome(s string) bool {
	rear := len(s) - 1
	for i, v := range s {
		if i == rear {
			break
		} else if v != rune(s[rear]) {
			return false
		}
		rear--
	}
	return true
}

完整程式碼:

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
func partition(s string) [][]string {
	return backTrack(s, []string{})
}
func backTrack(s string, set []string) [][]string {
	if len(s) == 0 {
		tmpSet := make([]string, len(set))
		copy(tmpSet, set)
		return [][]string{tmpSet}
	}
	var subString string
	var tmp [][]string
	var result [][]string
	for i, _ := range s {
		subString = s[:i+1]
		if !isPalindrome(subString) {
			continue
		}
		tmp = backTrack(s[i+1:], append(set, subString))
		result = append(result, tmp...)
	}
	return result
}
func isPalindrome(s string) bool {
	rear := len(s) - 1
	for i, v := range s {
		if i == rear {
			break
		} else if v != rune(s[rear]) {
			return false
		}
		rear--
	}
	return true
}

總結:

字串拆開後所有各別的子字串也都是回文並列出所有可能(可以參考解答思路的流程圖)，其實就是從開頭開始慢慢增長子字串，每次檢查最前面增長的那一段字串是否符合回文，如果不符合就繼續增長再做檢查，而如果符合則將後面其餘的子字串做遞回並重覆上述動作，直到最後剛開始開頭增長的子字串已經到達與原字串相同長度並列出所有符合回文條件的子字串組合。

分享到