字符串系列問題

分割回文串

回文串系列的一個(gè)通用解法是動(dòng)態(tài)規(guī)劃，在是否需要輸出回文串分割內(nèi)容的不同要求下，寫法也不同。

給定一個(gè)字符串 s，將 s 分割成一些子串，使每個(gè)子串都是回文串。
返回 s 所有可能的分割方案。
示例:
輸入: "aab"
輸出:
[
["aa","b"],
["a","a","b"]
]

class Solution:def partition(self, s: str) -> List[List[str]]:length = len(s)dp = [[False] * length for _ in range(length)]for i in range(length):for j in range(i + 1):if s[i] == s[j] and (i - j <= 2 or dp[j + 1][i - 1]):dp[j][i] = Trueresult = []def helper(index,temp):if index == length:result.append(temp)returnfor i in range(index,length):if dp[index][i]:helper(i + 1,temp + [s[index:i + 1]])helper(0,[])return result

這種問題就是注意分清楚回溯的邊界就好啦。

給定一個(gè)字符串 s，將 s 分割成一些子串，使每個(gè)子串都是回文串。
返回符合要求的最少分割次數(shù)。
示例:
輸入: "aab"
輸出: 1
解釋: 進(jìn)行一次分割就可將 s 分割成 ["aa","b"] 這樣兩個(gè)回文子串。

class Solution:def minCut(self, s: str) -> int:n = len(s)min_s = list(range(n))dp = [[False] * n for _ in range(n)]for i in range(n):for j in range(i + 1):if s[i] == s[j] and (i - j <= 2 or dp[j + 1][i - 1]):dp[j][i] = Trueif j == 0:min_s[i] = 0else:min_s[i] = min(min_s[i],min_s[j - 1] + 1)return min_s[-1]

不需要得到具體的分割方案時(shí)，只要記錄每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的分割次數(shù)即可。

單詞拆分

給定一個(gè)非空字符串 s 和一個(gè)包含非空單詞列表的字典 wordDict，在字符串中增加空格來構(gòu)建一個(gè)句子，使得句子中所有的單詞都在詞典中。返回所有這些可能的句子。
說明：
分隔時(shí)可以重復(fù)使用字典中的單詞。
你可以假設(shè)字典中沒有重復(fù)的單詞。
示例 1：
輸入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
輸出:
[
"cats and dog",
"cat sand dog"
]
示例 2：
輸入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
輸出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解釋: 注意你可以重復(fù)使用字典中的單詞。
示例 3：
輸入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出:
[]

注意記憶化遞歸的寫法。

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:if not wordDict:return []minLength,maxLength,length = len(wordDict[0]),len(wordDict[0]),len(s)wordDict = set(wordDict)for word in wordDict:minLength = min(minLength,len(word))maxLength = max(maxLength,len(word))def helper(index):if not index in lookup:result = []for i in range(minLength,min(maxLength,length - index) + 1):word = s[index:index + i]if word in wordDict:temp = [word + " " + j for j in helper(index + i)]result.extend(temp)lookup[index] = resultreturn lookup[index]lookup = {length:[""]}helper(0)return [i[:-1] for i in lookup[0]]

給定一個(gè)非空字符串 s 和一個(gè)包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。 說明：

拆分時(shí)可以重復(fù)使用字典中的單詞。
你可以假設(shè)字典中沒有重復(fù)的單詞。
示例 1：
輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因?yàn)?"leetcode" 可以被拆分成 "leet code"。
示例 2：
輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因?yàn)?"applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重復(fù)使用字典中的單詞。
示例 3：
輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false

同樣只要記錄每個(gè)字母位置的拆分次數(shù)即可。

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:""":type s: str:type wordDict: List[str]:rtype: bool"""breakp = [0]length = len(s)for i in range(length + 1):for j in breakp:if s[j:i] in wordDict:breakp.append(i)breakreturn breakp[-1] == len(s)

總結(jié)

以上是生活随笔為你收集整理的leetcode阶段总结——分割字符串类型的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。