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

Have you met this question in a real interview?

Yes

Example

Given"abb", return["abb", "bab", "bba"].

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

class Solution {
public:
    /**
     * @param str a string
     * @return all permutations
     */
    vector<string> stringPermutation2(string& str) {
            // Write your code here
            vector<string> res;
        sort(str.begin(), str.end());
        string tmp;
        vector<bool> flag(str.size(), false);
        findStr(res, tmp, str, flag);
        return res;
    }

    void findStr(vector<string> &res, string &tmp, string &str, vector<bool> &flag) {
        if (tmp.length() == str.length()) {
            res.push_back(tmp);
            return;
        }
        for (int i = 0; i < str.size(); ++i) {
            if (flag[i] || (i > 0 && str[i] == str[i - 1] && !flag[i - 1])) {
                continue;
            }
            flag[i] = true;
            tmp += str[i];
            findStr(res, tmp, str, flag);
            tmp.pop_back();
            flag[i] = false;
        }
    }
};