CompetitiveLin
diff --git a/‎Depth First Search/131. 分割回文串.md
Copy file name to clipboard
+68Lines changed: 68 additions & 0 deletions b/‎Depth First Search/131. 分割回文串.md
Copy file name to clipboard
+68Lines changed: 68 additions & 0 deletions
@@ -0,0 +1,68 @@
+#### 131. 分割回文串
+
+难度：中等
+
+---
+
+给你一个字符串 `s`，请你将 `s` 分割成一些子串，使每个子串都是
+
+ **回文串** 
+
+。返回 `s` 所有可能的分割方案。
+
+ **示例 1：** 
+
+```
+输入：s = "aab"
+输出：[["a","a","b"],["aa","b"]]
+```
+
+ **示例 2：** 
+
+```
+输入：s = "a"
+输出：[["a"]]
+```
+
+ **提示：** 
+
+*   `1 <= s.length <= 16`
+*   `s` 仅由小写英文字母组成
+
+---
+
+回溯：
+
+```Go
+func partition(s string) (ans [][]string) {
+    n := len(s)
+    path := []string{}
+    var dfs func(int)
+    dfs = func(i int) {
+        if i == n {
+            ans = append(ans, append([]string(nil), path...))
+            return 
+        }
+        for j := i; j < n; j++ {  // 枚举子串的结束位置
+            if isPalindrome(s, i, j) {
+                path = append(path, s[i : j + 1])
+                dfs(j + 1)
+                path = path[:len(path) - 1]
+            }
+        }
+    }
+    dfs(0)
+    return
+}
+
+func isPalindrome(s string, left, right int) bool {
+    for left < right {
+        if s[left] != s[right] {
+            return false
+        }
+        left++
+        right--
+    }
+    return true
+}
+```