@剣指offer(python)文字列の配列
11952 ワード
剣指offerブラシノート27(python)
タイトルの説明
文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.
考え方1
この問題は文字列の全配列,全配列を見ることができ,Python再帰と非再帰が全配列を実現することを別のブログで説明した(脱重と不脱重)
コード1
1つ目の方法は再帰です.再帰には2つの書き方があります.1つは交換で、もう1つは次のような書き方です.
ps:交換の書き方は別のブログで説明されています.
考え方2
2つ目の方法は,辞書順を用いたソート方法である.別のブログでも説明していました.
コード2
タイトルの説明
文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.
考え方1
この問題は文字列の全配列,全配列を見ることができ,Python再帰と非再帰が全配列を実現することを別のブログで説明した(脱重と不脱重)
コード1
1つ目の方法は再帰です.再帰には2つの書き方があります.1つは交換で、もう1つは次のような書き方です.
# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
# write code here
list = []
if len(ss) <= 1:
return ss
left = ss[0]
right = self.Permutation(ss[1:])
for word in right:
for i in range(len(word)+1):
if word[:i]+left+word[i:] not in list: #
list.append(word[:i]+left+word[i:])
list.sort() #
return list
ps:交換の書き方は別のブログで説明されています.
考え方2
2つ目の方法は,辞書順を用いたソート方法である.別のブログでも説明していました.
コード2
# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
# write code here
res = []
if ss == "":
return res
if len(ss) == 1:
return [ss]
strlist = []
for i in range(len(ss)):
strlist.append(ss[i])
strlist.sort()
res.append("".join(strlist))
size = len(strlist)
while True:
p = size - 1
while p >= 1 and strlist[p-1] >= strlist[p]:
p -= 1
if p == 0:
break
q = p
p -= 1
while q < size and strlist[q] > strlist[p]:
q += 1
q -= 1
self.swap(strlist,p,q)
self.reverse(strlist,p+1,size-1)
res.append("".join(strlist))
return res
def swap(self,strlist,p,q):
strlist[p],strlist[q] = strlist[q],strlist[p]
def reverse(self,array,i,j): #
if array is None or i < 0 or j < 0 or i >= j or len(array) < j + 1:
return
while i < j:
self.swap(array,i,j)
i += 1
j -= 1