題目：

判斷兩個字符串是否互為變形詞 字符串中數(shù)字子串的求和 去掉字符串中連續(xù)出現(xiàn)k個0的子串 判斷兩個字符串是否互為旋轉(zhuǎn)詞 將整數(shù)字符串轉(zhuǎn)成整數(shù)值 替換字符串中連續(xù)出現(xiàn)的指定字符串 字符串的統(tǒng)計字符串 判斷字符數(shù)組中是否所有的字符都只出現(xiàn)過一次 在有序但含有空的數(shù)組中查找字符串 字符串的調(diào)整與替換 翻轉(zhuǎn)字符串 數(shù)組中兩個字符串的最小距離 添加最少字符使字符串整體都是回文字符串 括號字符串的有效性和最長有效長度 公式字符串求值 0左邊必有1的二進制字符串數(shù)量 拼接所有字符串產(chǎn)生字典順序最小的大寫字符串 找到字符串的最長無重復(fù)字符子串 找到被指的新類型字符 最小包含子串的長度 回文最少分割數(shù) 字符串匹配問題 字典樹（前綴樹）的實現(xiàn)

（1）回文字符串 添加最少字符使字符串整體都是回文字符串 回文最少分割數(shù) 最長回文子串 判斷字符串本身是字符串或者刪除一個字符后成為回文串 刪除字符使字符串整體是回文串，最少多少種方案 （2）括號字符串 括號字符串的有效性和最長有效長度 有效的括號字符串（1）（2）（3）【三種題型】 括號最長有效長度 括號的分數(shù)（LeetCode856） 括號生成（LeetCode22） 括號匹配判斷 字符串解碼，去除括號（python） （3）字符串的求和 將整數(shù)字符串轉(zhuǎn)成整數(shù)值{python） 字符串中數(shù)字子串的求和 公式字符串求值 實現(xiàn)字符串數(shù)字的減法 基本計算器 （4）字符串反轉(zhuǎn) 翻轉(zhuǎn)字符串（python） 翻轉(zhuǎn)中間由各種符號隔開的字符串 單詞反轉(zhuǎn)（只允許O（1）空間） 旋轉(zhuǎn)字符串，n位字符串，循環(huán)右移m位，要求時間線性，空間n 把一個字符串的小寫字母放到前面，大寫放到后面，保持原有的順序。（python） （5）字符串替換 字符串的調(diào)整與替換 替換字符串中連續(xù)出現(xiàn)的指定字符串 （6）字符串刪除、排序 去掉字符串中連續(xù)出現(xiàn)k個0的子串 按照給定的字母序列對字符數(shù)組排序（python） （7）字符串的遍歷 字符串的統(tǒng)計字符串 判斷字符數(shù)組中是否所有的字符都只出現(xiàn)過一次 找到被指的新類型字符 如何截取包含中文的字符串（python） 在有序但含有空的數(shù)組中查找字符串 0左邊必有1的二進制字符串數(shù)量 一行代碼判斷字符串中是否有重復(fù)值（python） 統(tǒng)計字符串中連續(xù)的重復(fù)字符個數(shù)（python） （8）字符串的匹配 字符串匹配問題、贖金信（一個字符串字母是不是都在另一個字符串中） 判斷字符串A是否包含字符串B 正則化表達式匹配【含通配符】 字典樹（前綴樹）的實現(xiàn) （7）兩個字符串 判斷兩個字符串是否互為變形詞 判斷兩個字符串是否互為旋轉(zhuǎn)詞 判斷兩個字符串是否為換位字符串（python） 數(shù)組中兩個字符串的最小距離 求字符串的編輯距離（python） 兩個字符串的最長公共子序列 兩個字符最長公共子串（python） 拼接所有字符串產(chǎn)生字典順序最小的大寫字符串 特殊等價字符串組 求兩個絕對路徑的相對路徑（python） 如何查找到目標詞的最短鏈長度（python） 找到由其他單詞組成的最長單詞（python） （8）字符串的子串 找到字符串的最長無重復(fù)字符子串 重復(fù)子字符串 字符串中的第一個唯一字符 字符串的字典序最長子序列 去掉字符串中連續(xù)出現(xiàn)k個0的子串 最小包含子串的長度 （9）字符串的全排列（python）

?

?

?

一、判斷兩個字符串是否互為變形詞

題目：給定兩個字符串str1和str2，如果str1和str2中出現(xiàn)的字符種類一樣且每種字符出現(xiàn)的次數(shù)也一樣，則str1和str2互為變形詞。
請實現(xiàn)函數(shù)判斷兩個字符串是否互為變形詞。
舉例：
str1="123", str2="231", 返回true；
str1="123", str2="2331",返回false。

思路：

　1.?首先比較兩個字符串的長度，長度不同肯定是false。

　2.?如果長度相同，新建一個字典，用以存儲每個字符出現(xiàn)次數(shù)。

　3. 遍歷str1，在str1 中出現(xiàn)一次就加1，遍歷str2，在str2 中出現(xiàn)一次就減1，最后遍歷完str2沒有出現(xiàn)負值，就返回true。

代碼：

from collections import Counter def IsDeformation(str1,str2):if not str1 or not str2 or len(str1) != len(str2):return Falsecountstr1 = Counter(str1)for s2 in str2:if s2 in countstr1:countstr1[s2] -= 1if countstr1[s2] < 0:return Falseelse:return Falsereturn True str1 = '1234' str2 = '2313' IsDeformation(str1,str2)

?二、字符串中數(shù)字子串的求和

　給定一個字符串str，求其中全部數(shù)字串所代表的數(shù)字之和

　　1. 忽略小數(shù)點，“ A1.3 ” 表示的數(shù)字就是包含兩個數(shù)字 1 和 3

　　2. 緊貼數(shù)字的左邊出現(xiàn) “-”，其連續(xù)出現(xiàn)的數(shù)量如果為奇數(shù)，就視為 負，如果為偶數(shù)，就視為 正 “ A-1BC--23” 表示的是 -1 和 23

思路：時間復(fù)雜度是O(N),空間復(fù)雜度是O(1)

首先定義三個變量， res表示目前的累加和，num表示當前收集到的數(shù)字，布爾型變量flag表示將num加到res中，num是正還是負.

代碼：

def numSum(arr):if not arr:return 0num , res = 0 , 0flag = 1i = 0while i < len(arr):while i < len(arr) and arr[i] == '-':flag *= -1i += 1while i<len(arr) and arr[i].isdigit():num = num*10 + int(arr[i])i += 1if i<len(arr) and not arr[i].isdigit():i += 1if num:res += flag*num num ,flag = 0 , 1return res arr = 'A1.3' numSum(arr) a="A-1BC--23" numSum(a)

?三、去掉字符串中連續(xù)出現(xiàn)k個0的子串

給定一個字符串str和一個整數(shù)k，如果str中正好有連續(xù)的k個'0'字符出現(xiàn)時，把k個連續(xù)的'0'字符去除，返回處理后的字符串。

舉例：

str="A00B"，k=2，返回"AB"；

str="A0000B000"，k=3，返回"A0000B"。

思路：

?采用count記錄連續(xù)0的個數(shù)，若count==k，則將str連續(xù)的0刪除。

代碼：

def removeKzeros(arr,k):
??? if not arr or k == 0:
??????? return arr
??? count , i = 0 , 0
??? while i < len(arr):
??????? if arr[i] != '0':
??????????? i += 1
??????? while i < len(arr) and arr[i] == '0':
??????????? count += 1
??????????? i += 1
??????? if count and count == k:
??????????? arr = arr[:i-count]+arr[i:]
??????? count = 0
??? return arr
???????????
arr = 'A00B'
k = 2
removeKzeros(arr,k)
arr="A0000B000"
k=3
removeKzeros(arr,k)

?四、判斷兩個字符串是否互為旋轉(zhuǎn)詞

如果一個字符串str，把字符串str前面任意的部分挪到后面形成的字符串叫做str的旋轉(zhuǎn)詞。
如str="12345"，str的旋轉(zhuǎn)詞有"12345"、"23451"、"34512"、"45123"、"51234"。
給定兩個字符串a(chǎn)和b，請判斷a和b是否互為旋轉(zhuǎn)詞。
舉例：
a="cdab"，b="abcd"，返回true；
a="1ab2"，b="ab12"，返回false；
a="2ab1"，b="ab12"，返回true。
要求：
如果a和b長度不一樣，那么a和b必然不互為旋轉(zhuǎn)詞，可以直接返回false。
當a和b長度一樣，都為N時，要求解法的時間復(fù)雜度為O(N)。

思路：

將兩個b拼接在一起賦值給c，查看c中是否包含字符串a(chǎn)，若包含，則返回true；否則返回false。

代碼：

def isRotation(a,b):if len(a) != len(b):return Falsec = b+breturn (a in c)a = 'cdab' b = 'abcd' isRotation(a,b)

?五、將整數(shù)字符串轉(zhuǎn)成整數(shù)值

給定一個字符串str，如果str符合日常書寫的整數(shù)形式，并且屬于32位整數(shù)的范圍，返回所代表的整數(shù)值，否則返回0。
eg
str = “123”,返回123.
str = “023”,因為“023”不符合日常的書寫習慣，所以返回0.
str = “A23”,返回0；
str = “0”，返回0；
str= “2147483647”,返回2147483647.
str = “2147483648”，因為溢出了，所以返回0；
str = “-123”，返回-123；

思路：

空字符串輸入、正負符號、非法字符、整型溢出【最難處理】

?檢查日常書寫，非法字符

• 第一個既不是負號,也不是數(shù)字的情況，如：‘A12’
• 第一個是負號,但是整個字符串的長度只有1,或者負號后面跟個0的情況，如‘-“或者”-012“
• 以0開頭,而且整個字符串的長度大于1，如：‘012”
• 從第二個開始依次遍歷字符串,一旦出現(xiàn)不是數(shù)字的情況立即返回FALSE

字符轉(zhuǎn)數(shù)字操作

• • 字符串為空或者字符串的長度為0
  • 字符串中存在不合法的字符
  • 第一個字符是否為負號的情況

處理整數(shù)溢出：

當發(fā)生溢出時，取最大或最小的int值。即大于正整數(shù)能表示的范圍時返回MAX_INT：2147483647；小于負整數(shù)能表示的范圍時返回MIN_INT：-2147483648。

我們先設(shè)置一些變量：

• sign用來處理數(shù)字的正負，當為正時sign > 0，當為負時sign < 0
• n存放最終轉(zhuǎn)換后的結(jié)果
• c表示當前數(shù)字

處理溢出：

• 如果我們要轉(zhuǎn)換的字符串是"2147483697"，那么當我掃描到字符'9'時，判斷出214748369 > MAX_INT / 10 = 2147483647 / 10 = 214748364（C語言里，整數(shù)相除自動取整，不留小數(shù)），則返回0；
• 如果我們要轉(zhuǎn)換的字符串是"2147483648"，那么判斷最后一個字符'8'所代表的數(shù)字8與MAX_INT % 10 = 7的大小，前者大，依然返回0。

代碼：

#判斷是否為合法 def isValid(s):if s[0] != '-' and not s[0].isdigit():return Falseelif s[0] == '-' and (len(s) == 1 or s[1] == '0'):return Falseelif s[0] == '0' and len(s) > 1:return Falsefor i in range(len(s)):if not s[i].isdigit():return Falsereturn True def convert(s):#判斷為空if not s:return 0if not isValid(s):return 0sign = -1 if s[0] == '-' else 1q = 214748364 #-2^31 // 10maxr = 7res , cur = 0 , 0 start = 0 if sign == 1 else 1for i in range(start,len(s)): cur = int(s[i])if res > q or res == q and cur > maxr:return 0res = res * 10 + cur if sign and res == 2147483648:return 0return res * sign s = '2147483637' convert(s)

?六、替換字符串中連續(xù)出現(xiàn)的指定字符串

給定三個字符串str、from和to，已知from字符串中無重復(fù)字符，把str中所有from的子串全部替換成to字符串，對連續(xù)出現(xiàn)from的部分要求只替換成一個to字符串，返回最終的結(jié)果字符串

　　舉例：

　　　　str="123abc"，from="abc"，to="4567"，返回"1234567"

　　　　str="123"，from="abc"，to="456"，返回"123"

　　　　str="123abcabc"，from="abc"，to="X"，返回"123X"

思路：

先將str中含from的都替換成0*len(from)，然后將不等于0的用cur暫存，遇到0則 res + cur + to。

?

把str看作字符類型的數(shù)組，首先把str中from部分所有位置的字符編碼設(shè)為0（即空字符），如"12abcabca4"，from="abc"，處理后str=['1','2',0,0,0,0,0,0,'a','4']。
具體步驟如下：
1 生成整數(shù)變量match，標識目前匹配到from字符串的什么位置，初始時match=0；
2 從左到右遍歷str中每個字符，假設(shè)當前遍歷到str[i]；
3 若str[i]==from[match]，若match是from最后一個字符的位置，說明在str中發(fā)現(xiàn)了from字符串，則從i位置向前的M個位置，都把字符編碼設(shè)為0，M為from的長度，設(shè)置完成后令match=0；若match不是from最后一個字符的位置，則match++。繼續(xù)遍歷str的下一個字符；
4 若str[i]!=from[match]，說明匹配失敗，令match=0，即回到from開頭重新匹配。繼續(xù)遍歷str的下一個字符；

代碼：

def replace(s,f,to):if not s or f == None:return sarr = list(s)j = 0for i in range(len(s)):if s[i] == f[j]:if j == len(f)-1:s = s[:i-j] + '0' * len(f) + s[i+1:]# s[i-j+1:i+1] = '0' * len(f)j = 0else:j += 1else:j = 0res = ''cur = ''for i in range(len(s)):if s[i] != '0':cur = cur + s[i]if s[i] == '0' and (i == 0 or s[i-1] != '0'):res = res + cur + tocur = ''if cur:res = res + curreturn res s = '12abcabc3' f = 'abc' to = 'X' replace(s,f,to)

?七、字符串的統(tǒng)計字符串

思路：

一個變量count和一個結(jié)果變量res，若s[i] == s[i+1]，count +=1 ,否則count= 1

代碼：

def getCountString(s):if not s:return scount = 1res = ''for i in range(len(s)-1):if s[i] == s[i+1]:count+=1else:res = res + '_' + s[i]+'_'+str(count)count = 1if count == 1:res = res + '_' + s[-1] + '_' + '1'return res[1:] s = 'aaabbadddffc' getCountString(s)

?8、判斷字符數(shù)組中是否所有的字符都只出現(xiàn)過一次

要求1：采用字典來實現(xiàn)，比較簡單。

要求2：考察排序。

先將chas排序，排序后相同的字符就放在一起，易判斷有沒有重復(fù)字符。

重點選擇什么排序算法，保證空間復(fù)雜度為O（1）且時間復(fù)雜度較小。

• 時間O（N）、空間O（1）的沒有排序算法可以做到。
• 時間O（NlogN)：歸并【其實遞歸也需要輔助空間】、快排【空間最低O（logN）】、希爾【時間不穩(wěn)定，可能會變成O（N²）】、堆排序【可以】。
• 結(jié)果選擇堆排序，但要用非遞歸來實現(xiàn)，遞歸需要額外的空間。

?9、在有序但含有空的數(shù)組中查找字符串

10、字符串的調(diào)整與替換【倒著復(fù)制】

?

原問題思路：

• 遍歷第一遍：得到兩個信息，chas的左半?yún)^(qū)有多大，記為len，左半?yún)^(qū)的空格有多少，記為num。

可知最終長度為len+2*num，替換字母為%20.

• 從右往左遍歷第二遍：遇到字母復(fù)制到新長度最后位置，遇到空格則加入02%。

?補充問題思路：

從右往左倒著復(fù)制，遇到數(shù)字直接復(fù)制，遇到*不復(fù)制，當把所有數(shù)字復(fù)制完，把左半?yún)^(qū)全部設(shè)置成*即可。

11、翻轉(zhuǎn)字符串

思路：整體全部翻轉(zhuǎn)，再每個單詞翻轉(zhuǎn)

代碼：

def rotateWord(words):if words == None or len(words) == 0:returnwords = list(words[::-1])l , r = -1 , -1for i in range(len(words)):if words[i] != ' ':l = i if (i == 0 or words[i-1] ==' ') else lr = i if (i == len(words)-1 or words[i+1] == ' ') else rif l != -1 and r != -1:# reverse(words,l,r)words[l:r+1] = words[l:r+1][::-1]l , r = -1 , -1return ''.join(words)# def reverse(words,l,r): # tmp = '' # while l<r: # tmp = words[l] # words[l] = words[r] # words[r] = tmp # l += 1 # r -= 1 words = 'dogs love pigs' rotateWord(words)

思路一：三步反轉(zhuǎn)法 ：(X^TY^T)^T=YX

?

12、數(shù)組中兩個字符串的最小距離

思路：兩個變量分別更新str1和str2的位置，res記錄兩個變量差的最小值。

代碼：

import sys def minDistance(strs,str1,str2):if not strs or not str1 or not str2:return -1if str1 == str2:return 0last1 , last2 , res = -1 , -1 , sys.maxsizefor i in range(len(strs)):if strs[i] == str1:if last2 != -1:res = min(res,i - last2)last1 = iif strs[i] == str2:if last1 != -1:res = min(res,i - last1)last2 = ireturn res if res != sys.maxsize else -1 strs = ['3','1','3','3','3','2','3','1'] str1 = '1' str2 = '2' minDistance(strs,str1,str2)

進階問題：采用一個記錄來存儲結(jié)果，查詢時間記錄為O（1），但生成該記錄時間復(fù)雜度為O（N2），空間復(fù)雜度也為O（N2）。

該記錄為一個兩層字典，外層字典的value也是一個字典。

?13、添加最少字符使字符串整體都是回文字符串

思路：動態(tài)規(guī)劃時間O（N2）

（1）先求出最少需要添加多少個字符串才能補成回文串？

str的長度為N，生成N×N的dp矩陣，dp[i][j]的含義是子串str[i…j]最少添加幾個字符可以使str[i…j]整體都是回文串。dp[i][j]的求法如下：

• 如果i == j，說明此時只有一個字符，本身就是回文串，dp[i][j] = 0。
• 如果str[i…j]有兩個字符，如果這個字符相同dp[i][j] = 0。否則dp[i][j] = 1。
• 如果str[i…j]多于兩個字母，如果str[i] == str[j]。則dp[i][j] = dp[i+1][j-1]。否則，dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1。

（2）根據(jù)求得的dp矩陣來獲得一種回文結(jié)果：【類似最長公共子序列】

dp[0][N-1]的值代表整個字符串最少需要添加幾個字符，所以，如果最后的結(jié)果記為字符串res，res的長度為 N + dp[0][N-1]，然后依次設(shè)置res左右兩頭的字符。

代碼：

def getPalindrome(str1):def getdp(str1):dp = [[0 for i in range(len(str1))] for j in range(len(str1))]for j in range(1, len(str1)):dp[j-1][j] = 0 if str1[j-1] == str1[j] else 1for i in range(j-2, -1, -1):if str1[i] == str1[j]:dp[i][j] = dp[i+1][j-1]else:dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1return dpif str1 == None or len(str1) < 2:return str1dp = getdp(str1)res = [0 for i in range(len(str1)+dp[0][len(str1)-1])]i = 0j = len(str1) - 1resl = 0resr = len(res) - 1while i <= j:if str1[i] == str1[j]:res[resl] = str1[i]res[resr] = str1[j]i += 1j -= 1elif dp[i+1][j] < dp[i][j-1]:res[resl] = str1[i]res[resr] = str1[i]i += 1else:res[resl] = str1[j]res[resr] = str1[j]j -= 1resl += 1resr -= 1return ''.join(res)

?進階問題思路：假設(shè)str的長度為N，strlps的長度為M，則整體回文串的長度為2×N - M。整個過程類似 “剝洋蔥”。比如：

str = ‘A1BC22D1EF’ , str1 = '1221'，先剝1。A----1BC22D1------EF，1的外殼是left= A,right = EF,則左邊補（right逆序+left），右邊補（left逆序+right）。即FEA----1BC22D1-------AEF。

第二層為2，：FEA1----BC------22-------D----1AEF，left=BC，right= D。同理。

?

?

?

進階問題代碼：

def getPalindrome2(str1, strlps):if str1 == None or len(str1) == 0 or strlps == None or len(strlps) == 0:return res = [0 for i in range(2*len(str1)-len(strlps))]lstr = 0rstr = len(str1)-1llps = 0rlps = len(strlps)-1lres = 0rres = len(res)-1while llps <= rlps:temp1 = lstrtemp2 = rstrwhile str1[lstr] != strlps[llps]:lstr += 1while str1[rstr] != strlps[rlps]:rstr -= 1for i in range(temp1, lstr): res[lres] = str1[i]res[rres] = str1[i]lres += 1rres -= 1for i in range(temp2, rstr, -1):res[lres] = str1[i]res[rres] = str1[i]lres += 1rres -= 1res[lres] = str1[lstr]res[rres] = str1[rstr]lstr += 1rstr -= 1lres += 1rres -= 1llps += 1rlps -= 1return ''.join(res)

?14、括號字符串的有效性和最長有效長度

?原問題思路：采用一個變量記錄‘）’減去‘（’的差，若當前）-（>0則返回FALSE

?

補充問題思路：動態(tài)規(guī)劃，時間O（N），空間O（N）

dp[i]表示從0到第i個字符串的最長有效括號子串。

需同時考慮兩種情況：

包含關(guān)系（（）），dp[i] = dp[i-1] + 2【若 s [ i ] == ')' ,且 s [ i - dp [i-1] -1 ] == '('】

并列關(guān)系（）（），dp[i] = dp[i] + dp [ ?i - dp [i-1] -2 ]?

15、公式字符串求值

思路：采用棧存儲數(shù)字和加減符號，乘除在放入棧中已計算出結(jié)果。變量pre記錄數(shù)字。括號就遞歸。

1、遇到數(shù)字：采用pre變量保存。

2、遇到符號：存入棧中，存入之前先把棧中的乘除結(jié)果算出來

3、遇到左括號：遞歸計算

4、遇到右括號：計算棧中的結(jié)果。

?

?

17、拼接所有字符串產(chǎn)生字典順序最小的大寫字符串

思路：排序本身時間O（NlogN)

假設(shè)兩個字符分別是a，b。a和b拼起來的字符串表示為a.b，那么如果a.b的字典順序小于b.a，就把a放在前面，否則把b放在前面。每兩兩字符之間都按照這個標準進行比較，以此標準排序后，最后串起來的結(jié)果就是正確答案。

如 ‘b' , 'ba'，’b'和‘ba'排序后，’ba'應(yīng)與'b'位置交換，‘ba’在前，‘b’在后。

代碼：cmp_to_key是因為python3中沒有cmp這種用法，取代的。

def lowestString(chas):if chas == None or len(chas) == 0:return ""from functools import cmp_to_keychas = sorted(chas, key=cmp_to_key(lambda x,y: 1 if x+y > y+x else -1))return ''.join(chas) chas = ['b','ba','abc','dba'] lowestString(chas)

?

18、找到字符串的最長無重復(fù)字符子串

給定一個字符串str,返回str的最長無重復(fù)字符子串的長度。

舉例：

str = 'abcd'，返回4.

str = 'aabcb'，最長無重復(fù)字符子串為'abc'，返回3.

要求：

如果str的長度為N，請實現(xiàn)時間復(fù)雜度為O（N）的方法。

思路：時間O（N），空間O（N）

遍歷字符串中的每一個元素。借助一個輔助鍵值對來存儲某個元素最后一次出現(xiàn)的下標。用一個整形變量存儲當前無重復(fù)字符的子串開始的下標。

代碼：

def maxUnique(s):if s == None or s == '':return 0dic = {}res , start = 0 , -1for i in range(len(s)):if s[i] in dic:start = max(start,dic[s[i]])tmp = i - startdic[s[i]] = ires = max(res,tmp)return ress = 'ababcadc' maxUnique(s)

?19、找到被指的新類型字符

思路：從k-1位置開始向左統(tǒng)計大寫字母的數(shù)量，根據(jù)奇偶性來判斷。

代碼：

def test(s,k):if not s or s == '' or k < 0 or k >= len(s):return ''uNum = 0for i in range(k-1,-1,-1):if not s[i].isupper():breakuNum += 1if uNum % 2 == 1:return s[k-1:k+1]if s[k].isupper():return s[k:k+2]return s[k] s='aaABCDEcNCg' k = 7 test(s,k)

?

21、回文最少分割數(shù)【動態(tài)規(guī)劃】

給定一個字符串str,返回把str全部切成回文子串的最小分割數(shù)。

思路：動態(tài)規(guī)劃時間O（N2），空間O（N2）

定義動態(tài)規(guī)劃數(shù)組dp，dp[i]的含義是子串str[0…i]至少需要切割幾次，才能把str[0…i]全部切成回文子串。那么dp[len-1]就是最后的結(jié)果。

從左往右依次計算dp[i]的值，i 初始為0，具體計算過程如下：

1、假設(shè) j 處在 0 到 i 之間，如果str[j…i]是回文串，那么dp[i]的值可能是dp[j-1] + 1，其含義是在str[0…i]上，既然str[j…i]是回文串，那么它可以自己作為一個分割的部分，剩下的部分str[0…j-1]繼續(xù)做最經(jīng)濟的分割，也就是dp[j-1]的值。

根據(jù)步驟1的方式，讓 j 在 i 到 0 的位置上枚舉，那么所有可能中最小值就是dp[i]的值，即dp[i] = min{dp[j-1]+1 (0<= j <= i，且str[j…i]必須是回文串)}。

如何快速方便的判斷str[j…i]是否為回文串？

• • 定義一個二維數(shù)組p，如果p[j][i]為True，表示str[j…i]是回文串，否則不是。在計算dp過程中，希望能夠同步、快速的計算出矩陣p。
  • p[j][i]如果為True，一定來自以下三種情況：
    • <1>　str[j][i]由一個字符組成
      <2>　str[j][i]由兩個字符組成且兩個字符相等
      <3>　str[j][i]由多個字符組成，str[j] == str[i]且p[j+1][i-1] == True。
  • 在計算dp數(shù)組的過程中，位置i是從左向右依次計算的。而對于每一個i來說，又依次從 i 位置向左遍歷所有的位置，以此來決策dp[i]。所以對于p[j][i]來說，p[j+1][i-1]一定已經(jīng)計算過。

代碼：

import sys #從前往后遍歷 def minCut(str1):if str1 == None or str1 == "":return 0N = len(str1)p = [[False for i in range(N)] for j in range(N)]dp = [0 for i in range(N)]for i in range(N):dp[i] = sys.maxsizefor j in range(i, -1, -1):if str1[j] == str1[i] and (i-j < 2 or p[j+1][i-1]):p[j][i] = Truedp[i] = min(dp[i], 0 if j-1 == -1 else dp[j-1] + 1)return dp[-1]

?22、字符串匹配問題【動態(tài)規(guī)劃】

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/Lee-yl/p/10026176.html

總結(jié)

以上是生活随笔為你收集整理的算法65----字符串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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