String Permutation II (Ladder)

Description

Given a string, find all permutations of it without duplicates.

Example

Given "abb", return ["abb", "bab", "bba"].
Given "aabb", return ["aabb", "abab", "baba", "bbaa", "abba", "baab"].

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   class Solution {
   public:
    /**
     * @param str a string
     * @return all permutations
     */
    vector<string> stringPermutation2(string& str) {
        // Write your code here
        if (str.empty()) {
            return {""};
        }
        vector<string> result;
        vector<bool> used(str.size(), false);
        string row;
        sort(str.begin(), str.end());
        helper(str, result, row, used);
        return result;
    }
   private:
    void helper(string& str, vector<string>& result, 
        string& row, vector<bool> used
    ) {
        if (row.size() == str.size()) {
            result.push_back(row);
            return;
        }     
        int len = str.size();
        for (int i = 0; i < len; ++i) {
            // de-dup
            if (used[i]) {
                continue;
            }
            if (i > 0 && str[i-1] == str[i] && !used[i-1]) {
                continue;
            }
            row.push_back(str[i]);
            used[i] = true;
            helper(str, result, row, used);
            row.erase(row.begin() + row.size() - 1);
            used[i] = false;
        }
        return;        
    }
   };
   

Similar problems

x

Tags

x