剣指Offer(二十七):矩形カバー(C++/Python)
1647 ワード
タイトルの説明
文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.
説明を入力:
問題を解く構想.
文字列を2つの部分に分けて、一部は文字列の最初の文字で、もう一部は最初の文字の後のすべての文字で、再帰的に最初の文字の後のすべての文字の可能な配列を求めて、それから最初の文字と後ろの文字を1つずつ交換して、各文字を最初の可能な配列として求めます.ここで注意したいのは、文字列に重複文字がある可能性があるので、交換するときに判断を加えて、重複労働を避けることです.
C++版
Python版
文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.
説明を入力:
, 9( ), 。
問題を解く構想.
文字列を2つの部分に分けて、一部は文字列の最初の文字で、もう一部は最初の文字の後のすべての文字で、再帰的に最初の文字の後のすべての文字の可能な配列を求めて、それから最初の文字と後ろの文字を1つずつ交換して、各文字を最初の可能な配列として求めます.ここで注意したいのは、文字列に重複文字がある可能性があるので、交換するときに判断を加えて、重複労働を避けることです.
C++版
class Solution {
public:
vectorans;
vector Permutation(string str) {
ans.clear();
if(str.length() > 0)
MyPermutation(str, 0);
return ans;
}
void MyPermutation(string str, int cur){
if(cur == str.length()){
ans.push_back(str);
return;
}
for(int i = cur; i < str.length(); ++ i){
if(i != cur && str[i] == str[cur])
continue;
swap(str[i], str[cur]);
MyPermutation(str, cur+1);
}
}
};
Python版
class Solution:
def __init__(self):
self.ans = []
def Permutation(self, ss):
# write code here
if len(ss) > 0:
self.myPermutation(ss, 0)
return self.ans
def myPermutation(self, s, cur):
if cur == len(s):
self.ans.append(s)
return
for i in range(cur, len(s)):
if i != cur and s[i] == s[cur]:
continue
s_list = list(s)
s_list[i], s_list[cur] = s_list[cur], s_list[i]
s = ''.join(s_list)
self.myPermutation(s, cur+1)