Recursion / backtracking (middle)

One 、 Number of Islands

Solution 1 :dfs( recommend )

Depth-first search (dfs): Depth first search is generally used to traverse trees or graphs , Others with branches （ Such as two-dimensional matrix ） Also applicable . Its principle is to start from the initial point , Go all the way down the same branch , Until the end of the branch , Then go back to the upper level and continue to follow a branch to the end , So back and forth , Until all nodes are accessed .

• First judge the empty matrix
• Traverse the elements of every position of the matrix from top to bottom and from left to right , If the value is 1, Count the number of islands
• take 1 Change it to 0, Indicates that it has been counted , use dfs Judge whether the four directions are 1, Enter the four branches respectively and continue to modify
  

class Solution {
    
public:
    void dfs(vector<vector<char>>&v,int i,int j)
    {
    
        int n=v.size(),m=v[0].size();
        v[i][j]='0';
        // Recursion in four directions 
        if(i-1>=0&&v[i-1][j]=='1')
            dfs(v,i-1,j);
        if(i+1<n&&v[i+1][j]=='1')
            dfs(v,i+1,j);
        if(j-1>=0&&v[i][j-1]=='1')
            dfs(v,i,j-1);
        if(j+1<m&&v[i][j+1]=='1')
            dfs(v,i,j+1);
    }
    int solve(vector<vector<char> >& grid) {
    
        // write code here
        int n=grid.size();
        if(!n)
            return 0;
        int m=grid[0].size(),count=0;
        for(int i=0;i<n;i++)
        {
    
            for(int j=0;j<m;j++)
            {
    
                if(grid[i][j]=='1')
                {
    
                    count++;
                    dfs(grid,i,j);
                }
            }
        }
        return count;
    }
};

Time complexity ：O(nm), among m、n Is the length and width of the matrix , You need to traverse the entire matrix , Every time dfs The search needs to go through each value of 1 The elements of , But in the worst case, it just turns the whole matrix into 0, Therefore, it is equivalent to the worst ergodic matrix 2 Time
Spatial complexity ：O(nm), At worst, the whole matrix is 1, The recursive stack depth is m*n

Solution 2 :bfs

Breadth first search is different from depth first search , It is to access all other nodes directly connected to a node once in turn , Go deeper , Enter the node directly connected to other nodes .bfs We often use the first in, first out of the queue , Because starting from a certain node , We will queue the nodes directly connected to it , They enter first , Will pop up first , When they pop up, add the nodes directly connected to them , Thus, you can access by layer .

• The priority judgment matrix is empty
• • Traverse the elements of every position of the matrix from top to bottom and from left to right , If the value is 1, Count the number of islands
• Use bfs Will traverse the matrix encountered 1 And adjacent 1 Set as 0, Each time the queue enters the first 1, Traverse the queue , Explore whether there are four directions 1, Have set as 0, And the position coordinates enter the queue , Continue to traverse until the queue is empty

class Solution {
    
public:
    int solve(vector<vector<char> >& grid) {
    
        // write code here
        int n=grid.size();
        if(!n)
            return 0;
        int m=grid[0].size(),count=0;
        for(int i=0;i<n;i++)
        {
    
            for(int j=0;j<m;j++)
            {
    
                if(grid[i][j]=='1')
                {
    
                    count++;
                    grid[i][j]='0';
                    queue<pair<int,int>>q;
                    q.push({
    i,j});
                    while(!q.empty())//bfs
                    {
    
                        auto tmp=q.front();
                        q.pop();
                        int row=tmp.first,col=tmp.second;
                        if(row-1>=0&&grid[row-1][col]=='1')
                        {
    
                            q.push({
    row-1,col});
                            grid[row-1][col]='0';
                        }
                        if(row+1<n&&grid[row+1][col]=='1')
                        {
    
                            q.push({
    row+1,col});
                            grid[row+1][col]='0';
                        }
                        if(col-1>=0&&grid[row][col-1]=='1')
                        {
    
                            q.push({
    row,col-1});
                            grid[row][col-1]='0';
                        }
                        if(col+1<m&&grid[row][col+1]=='1')
                        {
    
                            q.push({
    row,col+1});
                            grid[row][col+1]='0';
                        }
                    }
                }
            }
        }
        return count;
    }
};

Time complexity ：O(n*m), among m、n Is the length and width of the matrix , You need to traverse the entire matrix , Every time bfs The search needs to go through each value of 1 The elements of , But in the worst case, it just turns the whole matrix into 0, Therefore, it is equivalent to the worst ergodic matrix 2 Time
Spatial complexity ：(min(n,m)),bfs The worst-case queue size is the smaller value of length and width

Two 、 Arrangement of strings

Solution 1 : violence dfs

• Recursive search for prime , For the first h layer , Enumerate the h A place , What subscript element should be filled
• Be careful ： Here, because the string may have duplicate elements , So we record the subscript , Because subscripts cannot be repeated （ It is equivalent to a hash function without hash conflict ）
• Then we also need to open one bool Array to record which subscripts have not been used , Ensure that the same subscript is used only once
• Recursive boundary conditions h==s.size(), Because the first h The layer representative is enumerating the h A place （ Namely front h-1 Locations have been enumerated ）, So the first h=s.size() The layer represents the front s.size()-1 Layers have been enumerated
• Back in time , Remember to restore the original state
  Time complexity , Each layer needs to enumerate whether all numbers can be used , Enumeration is required in total n layer

class Solution {
    
public:
   void dfs(int h,string&s,string&cur,set<string>&res,vector<int>&v)
   {
    
       if(h==s.size())// Recursive boundary 
       {
    
           res.insert(cur);
           return;
       }
       for(int i=0;i<s.size();i++)
       {
    
           if(!v[i])// If not used 
           {
    
               v[i]=1;// Mark as used 
               cur+=s[i];
               dfs(h+1,s,cur,res,v);// recursive 
               cur.pop_back();// to flash back 
               v[i]=0;
           }
           
       }
   }
    vector<string> Permutation(string str) {
    
        // write code here
        if(str.empty())
            return {
    };
        set<string>res;
        vector<int>v(str.size(),0);
        string cur;
        dfs(0,str,cur,res,v);
        return vector<string>({
    res.begin(),res.end()});
    }
};

The time complexity of this method is too high , It takes up a lot of space
Time complexity :O(n^n)
Spatial complexity :O(n)

Solution 2 :dfs Optimize

public:
  void dfs(int h,string&s,set<string>&res){
    
      if(h==s.size()-1){
    // Recursive boundary 
          res.insert(s);// Find a sort , And insert 
          return ;
      }
      for(int i=h;i<s.size();i++){
    // Suppose the original element is mapped to its subscript , Then we are searching for the full order of subscripts 
          swap(s[i],s[h]);
          dfs(h+1,s,res);// Go to the next level of recursion 
          swap(s[i],s[h]);// to flash back 
      }
  }
  vector<string>Permutation(string str) {
    
      if(str.empty())
          return {
    };
      set<string>res;// Because the title says str There may be repeating elements in , So we need to gather to remove the heavy , And play the role of sorting from small to large 
      dfs(0,str,res);// Start searching for Strings 
      return vector<string>({
    res.begin(),res.end()});//vector Iterator copy initialization , Just need the same type of element , It's not about the container 
  }
};

Time complexity :O(n^n)
Spatial complexity :O(n)

Solution 3 : recursive + to flash back ( recommend )

• First, sort the strings in dictionary order , Get the first permutation .
• Prepare an empty string to temporarily store the arrangement assembled during recursion . Use extra v An array is used to record where characters are added .
• Each recursion traverses the string from the beginning , Get characters to add ： First of all, according to the v Array , Elements that have been added cannot be added again ; meanwhile , If the current element str[i] The previous element on the same layer str[i-1] Same and str[i-1] Has been used , Nor does it need to be included in .
• Before going to the next level of recursion v The current position of the array is marked as used .
• It needs to be modified during backtracking v Array current position marker , At the same time, remove the element just added to the string ,
• When the length of the temporary string reaches the length of the original string, it is an arrangement .

class Solution {
    
public:
    void fun(vector<string>&res,string&str,string&tmp,vector<int>&v)
    {
    
        if(tmp.length()==str.length())
        {
    
            res.push_back(tmp);
            return ;
        }
        for(int i=0;i<str.length();i++)
        {
    
            if(v[i])// Have used 
                continue;
            if(i>0&&str[i-1]==str[i]&&!v[i-1])// repeat 
                continue;
            v[i]=1;// Mark 
            tmp.push_back(str[i]);
            fun(res,str,tmp,v);
            v[i]=0;// to flash back 
            tmp.pop_back();
        }
    }
    vector<string> Permutation(string str) {
    
        // write code here
        sort(str.begin(),str.end());
        vector<int>v(str.size(),0);
        vector<string>res;
        string tmp;
        fun(res,str,tmp,v);
        return res;
    }
};

Sorting with library functions does not require set Containers
Time complexity ：O(n∗n!)), All cases of full arrangement are n!, Each recursive process is to traverse the string to find elements , Here is O(n)
Spatial complexity ：O(n), The maximum depth of recursive stack is string length n, Temporary string tmp The space is also O(n),res It belongs to returning the necessary space *