【leetcode刷题之路】剑指Offer（3）——搜索与回溯算法

文章目录

- - 7 搜索与回溯算法

7 搜索与回溯算法

7.1 【BFS】剑指 Offer 32 - I - 从上到下打印二叉树

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/

这里借助队列来实现广度优先遍历，由于需要访问每一层的节点，而且这一层访问才可以访问下一层，所以可以考虑队列的先进先出，先把每一层的节点加入队列，然后把这一层的节点访问的同时，也把它们的左右子树加入队列，这样每一层访问完之后紧接着就是下一层的节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> q;
        if(root!=nullptr) q.push(root);
        while(!q.empty())
        {
            int n = q.size();
            for(int i=0;i<n;i++)
            {
                TreeNode *tmp = q.front();
                q.pop();
                ans.push_back(tmp->val);
                if(tmp->left!=nullptr) q.push(tmp->left);
                if(tmp->right!=nullptr) q.push(tmp->right); 
            }
        }
        return ans;
    }
};

7.2【BFS】剑指 Offer 32 - II - 从上到下打印二叉树 II

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/

这里借助队列来实现广度优先遍历，由于需要访问每一层的节点，而且这一层访问才可以访问下一层，所以可以考虑队列的先进先出，先把每一层的节点加入队列，然后把这一层的节点访问的同时，也把它们的左右子树加入队列，这样每一层访问完之后紧接着就是下一层的节点。以上一题不同的是每层的数要存放为一个向量，最后返回多个向量。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        if(root!=nullptr) q.push(root);
        while(!q.empty())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i=0;i<n;i++)
            {
                TreeNode *node = q.front();
                q.pop();
                tmp.push_back(node->val);
                if(node->left!=nullptr) q.push(node->left);
                if(node->right!=nullptr) q.push(node->right); 
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

7.3 【BFS】【双端队列】剑指 Offer 32 - III - 从上到下打印二叉树 III

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/

这里借助双端队列来实现广度优先遍历，由于需要访问每一层的节点，而且这一层访问才可以访问下一层，对于奇数层来说，访问的顺序是从左到右，而偶数层是从右到左，所以可以做如下操作：

奇数层：从左往右取队列元素，但是每个元素先取其左子树再取右子树，然后从队列末尾插入；
偶数层：从右往左取队列元素，但是每个元素先取其右子树再取左子树，然后从队列头部插入。

这样就可以保证每一层的顺序连在一起时之字形顺序了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        deque<TreeNode*> q;
        if(root!=nullptr) q.push_back(root);
        bool flag = true;
        while(!q.empty())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i=0;i<n;i++)
            {
                TreeNode *node;
                if(flag)
                {
                    node = q.front();
                    q.pop_front();
                    if(node->left!=nullptr) q.push_back(node->left);
                    if(node->right!=nullptr) q.push_back(node->right);
                }
                else
                {
                    node = q.back();
                    q.pop_back();
                    if(node->right!=nullptr) q.push_front(node->right);
                    if(node->left!=nullptr) q.push_front(node->left);
                }
                tmp.push_back(node->val);
            }
            flag = !flag;
            ans.push_back(tmp);
        }
        return ans;
    }
};

7.4 【BFS】剑指 Offer 26 - 树的子结构

https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/

这里把A的每个结点与B进行比较，如果结点相同则看它们的左右子树是否相同即可，这里借助自定义函数来判断A和B是否为包含关系，也就是A包含B，函数定义如下：

如果B为空，说明此时B的所有结点遍历完了，B为A的子树；
如果B不为空A为空，说明此时A的所有结点遍历完了但是B还有结点，则B不是A的子树；
如果此时A和B的结点相同，还要判断它们的左右子树是否相同。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool is_contain(TreeNode* A, TreeNode* B) {
        if(B==nullptr) return true;
        if(A==nullptr) return false;

        if(A->val==B->val) return is_contain(A->left,B->left) && is_contain(A->right,B->right);
        else return false;
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==nullptr || B==nullptr) return false;

        if(A->val==B->val && is_contain(A,B)) return true;
        else return isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
};

7.5 【递归】剑指 Offer 27 - 二叉树的镜像

https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/

直接交换每个结点的左右子树，然后递归返回即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==nullptr) return nullptr;
        swap(root->left,root->right);
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};

7.6 【递归】【双指针】剑指 Offer 28 - 对称的二叉树

https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/

利用双指针分别从树的左右子树往下判断是否对称，这里需要注意的是双指针最后必须同时为空才行，如果有一个先为空说明这棵二叉树是不对称的，同时双指针也要对称着向下移动，比如l左移r右移、l右移r左移。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode* l, TreeNode* r) {
        if(l==nullptr && r==nullptr) return true;
        if(l==nullptr || r==nullptr) return false;
        return l->val==r->val && check(l->left,r->right) && check(l->right,r->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root,root);
    }
};

7.7 【DFS】【回溯】【剪枝】剑指 Offer 12 - 矩阵中的路径

https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/

这里我们首先找到矩阵中和字符串的第一个字符对应的位置，然后从这个位置开始分别向上下左右深度搜索，直到找到与字符串完成对应的一条搜索路径即可，但是这里需要设置一些剪枝规则提前终止不必要的搜索：

如果访问越界了，需要提前终止搜索；
如果当前在矩阵中访问到的字符与目前在字符串中遍历到的字符不一样，需要提前终止搜索。

这里为了防止矩阵中的元素被重复使用，访问过的元素统一赋值为空，当这一轮搜索结束之后再用字符串赋值回去，避免影响判断。

class Solution {
private:
    int row,col;
public:
    bool exist(vector<vector<char>>& board, string word) {
        row = board.size();
        col = board[0].size();
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if(dfs(board,word,i,j,0)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
        //矩阵访问越界and当前访问字符不一致时，需要提前终止搜索，返回false
        if(i>=row || i<0 || j>=col || j<0 || board[i][j]!=word[k]) return false;
        //字符串遍历到最后一个字符，说明找到了一条路径，返回true
        if(k==word.size()-1) return true;
        //避免矩阵重复访问，已访问的赋值为空
        board[i][j] = ' ';
        //上下左右深度搜索
        bool flag = dfs(board,word,i-1,j,k+1) || dfs(board,word,i+1,j,k+1) || 
                    dfs(board,word,i,j-1,k+1) || dfs(board,word,i,j+1,k+1);
        //此轮搜索结束，已访问过的再赋值回去
        board[i][j] = word[k];
        return flag;
    }
};

7.8 【DFS】剑指 Offer 13 - 机器人的运动范围

https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

利用DFS解题，虽然机器人可以上下左右移动，但是最后算的是机器人可以到达多少个格子，所以可以把上下左右简化为下和右两个行动，并且设置一个数组visit来记录每个格子是否被访问过。这道题的难点在于行坐标和列坐标的位数之和如何快速计算，这里我们可以发现一个规律，假设坐标为18,19,20,21,22时，数位和分别为9,10,2,3,4，这里如果坐标不是10的倍数，那么数位和随着坐标数的增加依次加1，而当来到20时，数位和直接变成了2，比19的数位和少8，同理坐标29,30,31的数位和分别是11,3,4，所以可以总结出这样的规律：

如果坐标不是10的倍数，数位和较之前的坐标加1；
如果坐标是10的倍数。数位和较之前的坐标减8.

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visit(m,vector<bool>(n,false));
        return dfs(0,0,0,0,visit,m,n,k);
    }

    int dfs(int i, int j, int si, int sj, vector<vector<bool>> &visit, int m, int n, int k) {
        if(i<0 || i>=m || j<0 || j>=n || si+sj>k || visit[i][j]) return 0;
        visit[i][j] = true;
        int new_si = (i+1)%10 != 0 ? si+1 : si-8;
        int new_sj = (j+1)%10 != 0 ? sj+1 : sj-8;
        return 1 + dfs(i,j+1,si,new_sj,visit,m,n,k) + dfs(i+1,j,new_si,sj,visit,m,n,k);
    }
};

7.9 【DFS】【递归】剑指 Offer 34 - 二叉树中和为某一值的路径

https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

利用DFS解题，顺着根结点先往一个子结点方向遍历，然后再去遍历另一个，这里的难点在于精准判断是否达到目标和，一共需要以下几个条件：

截止目前的路径上的val之和等于target；
目前结点是叶子结点，也就是该结点的左右结点都为空。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        vector<int> path;
        dfs(root,target,path);
        return ans;
    }

    void dfs(TreeNode* root, int target, vector<int> path) {
        if(root==nullptr) return;
        path.push_back(root->val);
        if(root->val==target && root->left==nullptr && root->right==nullptr)
        {
            ans.push_back(path);
            return;
        }
        dfs(root->left,target-root->val,path);
        dfs(root->right,target-root->val,path);
    }
};

7.10 【DFS】【递归】【双指针】剑指 Offer 36 - 二叉搜索树与双向链表

https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

这道题其实就是把给出的这个二叉树变成中序遍历的结果输出，然后在中序遍历的过程中改变左右子树的指向即可，使之变成双向循环链表，这里借助双指针来构造循环链表，head指向循环链表的开始，pre指向中序遍历过程中访问到的每个结点的前序结点，按照中序遍历的过程进行DFS，遍历到最下面的左子树时，开始构造链表，此时左子树应该是当前root的前驱，这样就构造出了一个循环，然后依次往上返回构造其他循环，最后要把头尾连接起来。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node *head=nullptr, *pre=nullptr;

    Node* treeToDoublyList(Node* root) {
        if(root==nullptr) return root;
        dfs(root);
        head->left = pre;
        pre->right = head;
        return head;
    }

    void dfs(Node* root) {
        if(root==nullptr) return;
        dfs(root->left);
        if(pre!=nullptr) pre->right = root;
        else head = root;
        root->left = pre;
        pre = root;
        dfs(root->right);
    }
};

7.11 【DFS】剑指 Offer 54 - 二叉搜索树的第k大节点

https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

这道题是找第k大的结点，二叉搜索树的中序遍历结果是从小到大排序，所以其实就是对二叉搜索树进行倒过来的中序遍历，每遍历一个元素k–，当k为0时就是最终结果。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    int kthLargest(TreeNode* root, int k) {
        dfs(root,k);
        return ans;
    }

    void dfs(TreeNode* root,int &k) {
        if(root==nullptr) return;
        dfs(root->right,k);
        k--;
        if(k==0) ans = root->val;
        dfs(root->left,k);
    }
};

7.12 【DFS】剑指 Offer 55 - I - 二叉树的深度

https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/

考察深度优先遍历，从上往下深度搜索，没找到一个节点就把当前的深度dpt加1，最后取最大的那个dpt即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int depth = 1;
    int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        dfs(root,0);
        return depth;
    }
    
    void dfs(TreeNode* root, int dpt) {
        if(root==nullptr)
        {
            depth = max(depth,dpt);
            return;
        }
        dpt++;
        dfs(root->left,dpt);
        dfs(root->right,dpt);
    }
};

7.13 【DFS】剑指 Offer 55 - II - 平衡二叉树

https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/

采用自底向上的方法，首先判断最下面的节点是否满足平衡二叉树的条件，不满足就把当前高度赋值为-1，这样一步步从下往上递增，最后只需看根结点的高度是多少即可，如果采用自顶向下的话则会存在某些节点多次计算高度，会增加时间复杂度。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(depth(root)!=-1) return true;
        else return false;
    }

    int depth(TreeNode* root) {
        if(root==nullptr) return 0;
        int left_depth = depth(root->left);
        int right_depth = depth(root->right);
        if(left_depth == -1 || right_depth == -1 || abs(left_depth - right_depth) > 1)
        {
            return -1;
        }
        else return max(left_depth,right_depth) + 1;
    }
};

7.14 【位运算】剑指 Offer 64 - 求1+2+…+n

https://leetcode.cn/problems/qiu-12n-lcof/

求和公式为sum=n*(n+1)/2，这里为什么用bool呢，其实用char也行，因为它们都占用一个字节，意思就是构造了一个n*(n+1)的数组，然后先计算这个数组一共多少字节，对于除2操作直接位运算就行了。

class Solution {
public:
    int sumNums(int n) {
        bool ans[n][n+1];
        return sizeof(ans)>>1;
    }
};

7.15 【DFS】【递归】剑指 Offer 68 - I - 二叉搜索树的最近公共祖先

https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

这道题需要明白一点，就是x的值一定是在p和q之间的，所以在深度遍历时只需比较当前根节点的值和p、q的值的大小即可，如果当前节点的值比p和q都大，说明最近公共祖先在左子树，如果当前节点的值比p和q都小，说明最近公共祖先在右子树，如果都不满足说明目前找到的就是最近公共祖先了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if(root->val > p->val && root->val > q->val)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else if(root->val < p->val && root->val < q->val)
        {
            return lowestCommonAncestor(root->right,p,q);
        }
        else return root;
    }
};

7.16 【DFS】剑指 Offer 68 - II - 二叉树的最近公共祖先

https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

这题为一般二叉树中找最近公共祖先，首先要明确公共祖先的判断标准，共有以下三点：

(1)p和q在二叉树两侧（也就是一个在左子树一个在右子树），则找最近的root结点；
(2)p和q在二叉树同侧（也就是同在左子树或者右子树），则找p或者q；

下面定义双指针left和right来判断目前节点的左右子树中是否有p和q，并给出以下判断标准：

(1)如果left和right均不为空，说明p和q一个在左子树一个在右子树，返回当前root节点；
(2)如果left为空，right不为空，说明p和q都在右子树中，返回right；
(3)如果left不为空，right为空，说明p和q都在左子树中，返回left。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr || root==p || root==q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if(left==nullptr) return right;
        if(right==nullptr) return left;
        return root;
    }
};

7.17 【DFS】【模拟】剑指 Offer 37 - 序列化二叉树

https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/

本题主要实现两个功能，分别是二叉树的序列化和反序列化，也就是给定字符串变成二叉树，或者给定二叉树变成字符串，下面分开来介绍实现思路：
（1）二叉树->字符串
这个其实就是对二叉树进行中序遍历即可，然后把每个节点的值保存到字符串中，难点在于如何把整数转变成字符串，因为这里的数值可能是多位数或者负数，所以这里定义了一个函数int_to_str()来实现将整数转变为字符串，同时在函数tree_to_str()中实现将二叉树转为字符串，这里注意每个数值后面要加上逗号’,‘。
（2）字符串->二叉树
这个就比较难了，首先要把字符串中的字符转为数字，这里通过自定义函数str_to_int()来实现，接下来就是为每一个生成的数值构造一个节点，按照中序遍历的情况依次构造二叉树，当上述准备工作完成之后，下面就是要对给定的字符串进行切割，分割标准为逗号’,'，遍历是每遇到逗号说明是一个节点，然后把这个节点通过上述两步操作插入到二叉树中即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
private:
        string int_to_str(int num) {
        bool flag = true;
        string ans;
        if(num < 0)
        {
            num = -num;
            flag = false;
        }
        while(num)
        {
            ans.insert(ans.begin(), num % 10 + '0');
            num /= 10;
        }
        if(flag==false) ans.insert(ans.begin(),'-');
        return ans;
    }

    int str_to_int(string s) {
        int idx = 0;
        bool flag = true;
        int ans = 0;
        if(s[idx]=='-')
        {
            flag = false;
            idx++;
        }
        while(idx < s.size())
        {
            ans = s[idx] - '0' + ans * 10;
            idx++;
        }
        if(flag==false) ans = -ans;
        return ans;
    }

    void tree_to_str(TreeNode* root, string& str) {
        if(root==nullptr)
        {
            str += "/,";
            return;
        }
        str += int_to_str(root->val);
        str += ",";
        tree_to_str(root->left, str);
        tree_to_str(root->right, str);
    }

    TreeNode* str_to_tree(vector<string>& s, int& idx) {
        if(s[idx]=="/") return nullptr;
        int val = str_to_int(s[idx]);
        TreeNode* root = new TreeNode(val);
        root->left = str_to_tree(s, ++idx);
        root->right = str_to_tree(s, ++idx);
        return root;
    }

public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ans;
        tree_to_str(root,ans);
        return ans;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> s;
        int idx = 0;
        while(idx < data.size())
        {
            int tmp = idx;
            while(data[idx]!=',') idx++;
            string now = data.substr(tmp, idx - tmp);
            s.push_back(now);
            idx++;
        }
        idx = 0;
        TreeNode* root = str_to_tree(s, idx);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

7.18 【DFS】【回溯】【模拟】剑指 Offer 38 - 字符串的排列

https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/

这题难点在于如何保证字符不重复遍历，同时也要保证最后得到的字符串里面没有重复的字符串，这里考虑到可能原始的字符串里会有一些重复字符，所以先对原始的字符串进行排序，然后定义一个数组visited来保存每一位是否被访问过，而在深度遍历的时候，对于每次访问的字符，也要判断它是否为重复的字符，防止重复的字符被多次访问，但最后其实都是得到的同一个字符串，最后本次遍历完之后还要把临时字符串tmp和visited置回原来的状态。

class Solution {
public:
    vector<string> ans;
    vector<int> visited;

    void dfs(string &s, int i, int length, string &tmp) {
        if(i==length)
        {
            ans.push_back(tmp);
            return;
        }

        for(int j=0;j<length;j++)
        {
            if(visited[j] || (j>0 && !visited[j-1] && s[j-1]==s[j])) continue;

            visited[j] = 1;
            tmp.push_back(s[j]);

            dfs(s,i+1,length,tmp);
            tmp.pop_back();
            visited[j] = 0;
        }
    }

    vector<string> permutation(string s) {
        int length = s.size();
        visited.resize(length);
        string tmp;

        sort(s.begin(),s.end());
        dfs(s,0,length,tmp);

        return ans;
    }
};