Commitb4db7e4

committed

Create 131. 分割回文串.md

1 parent0749f83 commitb4db7e4Copy full SHA for b4db7e4

File tree

+68

-0

lines changed

+68

-0

lines changed

Lines changed: 68 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,68 @@`
	`1`	`+####131. 分割回文串`
	`2`	`+`
	`3`	`+难度：中等`
	`4`	`+`
	`5`	`+---`
	`6`	`+`
	`7`	+给你一个字符串`s`，请你将`s` 分割成一些子串，使每个子串都是
	`8`	`+`
	`9`	`+回文串`
	`10`	`+`
	`11`	+。返回`s` 所有可能的分割方案。
	`12`	`+`
	`13`	`+示例 1：`
	`14`	`+`
	`15`	+```
	`16`	`+输入：s = "aab"`
	`17`	`+输出：[["a","a","b"],["aa","b"]]`
	`18`	+```
	`19`	`+`
	`20`	`+示例 2：`
	`21`	`+`
	`22`	+```
	`23`	`+输入：s = "a"`
	`24`	`+输出：[["a"]]`
	`25`	+```
	`26`	`+`
	`27`	`+提示：`
	`28`	`+`
	`29`	+*`1 <= s.length <= 16`
	`30`	+*`s` 仅由小写英文字母组成
	`31`	`+`
	`32`	`+---`
	`33`	`+`
	`34`	`+回溯：`
	`35`	`+`
	`36`	+```Go
	`37`	`+funcpartition(sstring) (ans [][]string) {`
	`38`	`+n:=len(s)`
	`39`	`+path:= []string{}`
	`40`	`+vardfsfunc(int)`
	`41`	`+ dfs =func(iint) {`
	`42`	`+if i == n {`
	`43`	`+ ans =append(ans,append([]string(nil), path...))`
	`44`	`+return`
	`45`	`+ }`
	`46`	`+forj:= i; j < n; j++ {// 枚举子串的结束位置`
	`47`	`+ifisPalindrome(s, i, j) {`
	`48`	`+ path =append(path, s[i : j +1])`
	`49`	`+dfs(j +1)`
	`50`	`+ path = path[:len(path) -1]`
	`51`	`+ }`
	`52`	`+ }`
	`53`	`+ }`
	`54`	`+dfs(0)`
	`55`	`+return`
	`56`	`+}`
	`57`	`+`
	`58`	`+funcisPalindrome(sstring,left,rightint)bool {`
	`59`	`+for left < right {`
	`60`	`+if s[left] != s[right] {`
	`61`	`+returnfalse`
	`62`	`+ }`
	`63`	`+ left++`
	`64`	`+ right--`
	`65`	`+ }`
	`66`	`+returntrue`
	`67`	`+}`
	`68`	+```

Comments

(0)