class Solution {
public:
    /*
     * @param str: A string
     * @return: all permutations
     */
    vector<string> stringPermutation2(string &str) {
        // write your code here
        vector<string> results;
        if (str == "") {
            results.push_back(str);
            return results;
        }
        //sort(str.begin(), str.end());
        vector<bool> visited (str.length(), false);
        string cur = "";
        dfsHelper(str, cur,results, visited);
        return results;
    }
    void dfsHelper(string &str, string &cur, vector<string> & results, vector<bool> &visited) {
        if (cur.length() == str.length()) {
            results.push_back(cur);
            return;
        }
        for(int i = 0; i < str.length(); i++) {
            if (visited[i]) {
                continue;
            }
            if (i > 0 && str[i-1] == str[i] && !visited[i-1]) {
                continue;
            }
            visited[i] = true;
            cur += str[i];
            dfsHelper(str, cur, results, visited);
            visited[i] = false;
            cur = cur.substr(0, cur.length() - 1);
        }
    }

};