需要用到动态规划法,固定它的状态序列,然后将后续需要插入的字符挨个插入。例如ab中将c插入的话,有3个位置:前中后,分别是:
(c)ab,a(c)b,和ab(c),此时需要用到insterster()函数。具体代码如下:
def insertstr(s, addstr): newstr = [] for i in range(len(s)+1): newstr.append(s[:i] + addstr + s[i:])///这里主要是切分字符,然后append到新的列表中 return newstr def dp(state, addstr): newstate = [] for oldstr in state: new = insertstr(olestr, addstr) //调用insertstr函数 for s in new: //遍历ab,ba开头的所有情况 newstate.append(s) return newstate class Slotion: def Permutation(self, ss): nextstate = [ss[0]] for addstr in ss[1:]: nextstate = dp(nextstate, addstr) //调用dp函数 a = list(set(nextstate)) //set是变成字典,可以去重,因为返回的是list a.sort() //题目要求排序 return a