剣指Offer(二十七):矩形カバー(C++/Python)

1647 ワード

タイトルの説明
文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列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)