leetcode Question 133: Palindrome Partitioning II

Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Analysis:
This is a DP problem! Also it is a double DP problem!
Why? Because, if we use the same algorithm in the Palindrome Partitioning I, definitely it will expire the time limit. When you are facing the problem asking "return the minimum/maximum, best, shortest...", it is also a good direction targeting the DP (sometimes greedy also works fine). If you are not familiar with DP problem, here is a very good reading from topcoder. Generally speaking, DP is not very easy, and most of the company interviews will NOT cover the DP, so don't worry too much.

For this problem, firstly we consider the main part.
It is a good way to look for the "state", and the "optimal solution" based on that state, to solve the DP problem. In other words, if you found the correct state, and the function of the state representing the optimal solution, all you need is some loops and initialization implementing the algorithm.

Here the state is not too hard ----  minimum cut.   Define res[i] = the minimum cut from 0 to i in the string.
The result w =e need eventually is res[s.size()-1].
We know res[0]=0. Next we are looking for the optimal solution function f.
For example, let s = "leet".
f(0) = 0;  // minimum cut of str[0:0]="l", which is a palindrome, so not cut is needed.
f(1) = 1; // str[0:1]="le" How to get 1?
                 f(1) might be:  (1)   f(0)+1=1, the minimum cut before plus the current char.
                                       (2)   0, if str[0:1] is a palindrome  (here "le" is not )
f(2) = 1; // str[0:2] = "lee" How to get 2?
                f(2) might be:   (1)  f(1) + 1=2
                                       (2)  0, if str[0:2] is a palindrome (here "lee" is not)
                                       (3)  f(0) + 1,  if str[1:2] is a palindrome, yes! 
f(3) = 2; // str[0:3] = "leet" How to get 2?
                f(3) might be:   (1)  f(2) + 1=2
                                       (2)  0, if str[0:3] is a palindrome (here "leet" is not)
                                       (3)  f(0) + 1,  if str[1:3] is a palindrome (here "eet" is not)
                                       (4)  f(1) + 1,  if str[2:e] is a palindrome (here "et" is not)
OK, output f(3) =2 as the result.

So, the optimal function is:

f(i) = min [  f(j)+1,  j=0..i-1   and str[j:i] is palindrome
                    0,   if str[0,i] is palindrome ]

The above algorithm works well for the smaller test cases, however for the big cases, it still cannot pass.
Why? The way we test the palindrome is time-consuming.

Also using the similar DP idea, we can construct the look-up table before the main part above, so that the palindrome testing becomes the looking up operation. The way we construct the table is also the idea of DP.
e.g.  mp[i][j]==true if str[i:j] is palindrome.
       mp[i][i]=true;
       mp[i][j] = true if str[i]==str[j] and (mp[i+1][j-1]==true or j-i<2 )  j-i<2 ensures the array boundary.

So, using this scheme to test the palindrome helps improve the efficiency and thus we can pass all the test cases. Details see the code below.


Code:

class Solution {
public:
    int minCut(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int>res(s.size(),0);
        bool mp[s.size()][s.size()];
        
        for (int i=s.size()-1;i>=0;i--){
            for (int j=i;j<s.size();j++){
                if ((s[i]==s[j]) && (j-i<2 || mp[i+1][j-1])){
                    mp[i][j]=true;
                }else{
                    mp[i][j]=false;
                }
            }
        }
            
        for (int i=0;i<s.size();i++){
            int ms = s.size();
            if (mp[0][i]){
                res[i]=0;
            }else{
                for (int j=0;j<i;j++){
                    if (mp[j+1][i] && ms>res[j]+1 ) {
                            ms=res[j]+1;
                    } 
                }
                res[i]=ms;
            }
        }   
        return res[s.size()-1];
    }
};

leetcode Question 131: Surrounded Regions

Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region .

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Analysis:

Search is a good way to solve this problem!
First and easy thought might, scan all the element, if meets 'O', looking for a path to the boundary, if not exist, put it to 'X'. To look for the path, if all the four directions all have no way out, this element has no way out. The DFS can be used.  See code(small case) below. Actually, it only cannot pass the last big test case (where 250x250 matrix is provided).

However, it will not pass the big test, because the complexity is too high. One common thought is to use BFS instead of DFS, which use more space, but less time.

So how BFS is conducted, we can think from out to inside. Because the boundary 'O' are definitely "live" (have a path out) element, so, we BFS from each 'O' in the boundary, mark all its four directions (where is also 'O') as "live". If you think here, you almost done, the standard BFS using a queue (here I use vector for simplicity) can solve the problem. Last step is to flip "O" to "X" because there is no way out, and flip "P"(live) to "O", because it has a path out. See code (big case) for details. All the test cases are passed.

Code (C++):

class Solution {
public:
     void solve(vector<vector<char>> &board) {
        int row = board.size();  //get row number
        if (row==0){return;}
        int col = board[0].size(); // get column number
        
        vector<vector<bool> > bb(row, vector<bool>(col)); //result vector
        
        queue<pair<int,int> > q; // queue for BFS
        
        //search "O" from 1st row
        for (int i=0;i<col;i++){
            if (board[0][i]=='O'){
                q.push(make_pair(0,i));
                bb[0][i]=true;
            }
        }
        
        //search "O" from 1st column
        for (int i=0;i<row;i++){
            if (board[i][0]=='O'){
                q.push(make_pair(i,0));
                bb[i][0]=true;
            }
        }
        
        //search "O" from last row
        for (int i=0;i<col;i++){
            if (board[row-1][i]=='O'){
                q.push(make_pair(row-1,i));
                bb[row-1][i]=true;
            }
        }
        
        //search "O" from last column
        for (int i=0;i<row;i++){
            if (board[i][col-1]=='O'){
                q.push(make_pair(i,col-1));
                bb[i][col-1]=true;
            }
        }
        
        //BFS
        int i,j; // current position
        while (!q.empty()){
            //get current live "O"
            i = q.front().first;
            j = q.front().second;
            
            //pop up queue
            q.pop(); 
            
            //search four directions
            if (i-1>0 && board[i-1][j]=='O' && bb[i-1][j]==false){bb[i-1][j]=true; q.push(make_pair(i-1,j));} //top
            if (i+1<row-1 && board[i+1][j]=='O'&& bb[i+1][j]==false){bb[i+1][j]=true; q.push(make_pair(i+1,j));} // bottom
            if (j-1>0 && board[i][j-1]=='O'&& bb[i][j-1]==false){bb[i][j-1]=true; q.push(make_pair(i,j-1));} // left
            if (j+1<col-1 && board[i][j+1]=='O'&& bb[i][j+1]==false){bb[i][j+1]=true; q.push(make_pair(i,j+1));} // right
        }
        
        //Get result
        for (int i=0;i<row;i++){
            for (int j=0;j<col;j++){
                if (board[i][j]=='O'&&bb[i][j]==false){
                    board[i][j]='X';
                }
            }
        }
        
        return;
           
    }
};

Code(Python):

class Solution:
    # @param board, a 2D array
    # Capture all regions by modifying the input board in-place.
    # Do not return any value.
    def solve(self, board):
        row = len(board)
        if row==0:
            return
        col = len(board[0])    
        bb = [[False for j in xrange(0,col)] for i in xrange(0,row)]
        que = []
        for i in xrange(0,col):
            if board[0][i]=='O':
                bb[0][i]=True
                que.append([0,i])
            if board[row-1][i]=='O':
                bb[row-1][i]=True
                que.append([row-1,i])
                
        for i in xrange(0,row):
            if board[i][0]=='O':
                bb[i][0]=True
                que.append([i,0])
            if board[i][col-1]=='O':
                bb[i][col-1]=True
                que.append([i,col-1])
        
        while que:
            i = que[0][0]
            j = que[0][1]
            que.pop(0)
            if (i-1>0 and board[i-1][j]=='O' and bb[i-1][j]==False):
                bb[i-1][j]=True
                que.append([i-1,j])
            if (i+1<row-1 and board[i+1][j]=='O' and bb[i+1][j]==False):
                bb[i+1][j]=True
                que.append([i+1,j])
            if (j-1>0 and board[i][j-1]=='O' and bb[i][j-1]==False):
                bb[i][j-1]=True
                que.append([i,j-1])
            if (j+1<col-1 and board[i][j+1]=='O' and bb[i][j+1]==False):
                bb[i][j+1]=True
                que.append([i,j+1])
                
        for i in xrange(0,row):
            for j in xrange(0,col):
                if board[i][j]=='O' and bb[i][j]==False:
                    board[i][j] = 'X'
        
        return
                
        

leetcode Question 132: Palindrome Partitioning

Palindrome Partitioning 

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Analysis:
When face the "return all", "get all ", "find all possible", "find the total number of", an idea is to use the recursion. Same as this problem!

To get the all the partitions of a string s:
1. find all the palindromes in substring s[0], and all the palindromes in substring s[1:end]
2. find all the palindromes in substring s[0:1], and all the palindromes in substring s[2:end]
...
find all the palindromes in substring s[1:end-1], and all the palindromes in substring s[end]

So the problem is quite clear, when we do recursion, two things should be considered:
1. stop condition:  when the search goes to the last position in the string
2. for loop or while loop:   for position=current start position to the end.

This problem is not complex, see the code below and you will understand the idea:


Code:

class Solution {
public:

    bool valid(string &str, int st, int ed){
        while (st<ed){
            if (str[ed]!=str[st]){
                return false;
            }else{
                st++;
                ed--;
            }
        }
        return true;
    }

    
    void find(string s, int st, vector<string> &r, vector<vector<string> > &res){
        if (st>=s.size()){
            res.push_back(r);
        }else{
        for (int i=st;i<s.size();i++){            
            if (valid(s,st,i)){
                r.push_back(s.substr(st,i-st+1));
                find(s,i+1,r,res);        
                r.pop_back();
            }
            
        }
        }  
    }

    vector<vector<string>> partition(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<string> > res;
        vector<string> r;
        find(s,0,r,res);
        return res;    
    }
};

[Re-View]Hash Table (Basics)

Hash table Basics

Intro

The concept, usage and implementations of Hash table are always used in Software Engineer interviews. From the interview guidance of Google, there is an requirement of hash table. It is said "Hashtables: Arguably the single most important data structure known to mankind." There is indeed a bunch of knowledge and techniques for hashtables (hash function, collision, etc.), but from the interview perspective, it is not possible to test the thorough and complete skills of hashtables in a short interview. Take this advantage, in this post, I'd like to learn the basics of hash tables, and try to implement sample code.

What is Hash Table?

It is a very common but often occurred question in IT interviews. I generalize the concept in my own words: " Hash table, is a data structure, which stores key-value pairs, the access of value by key can be O(1) time, a hash function is used to map the key to the index of the value."

You can find many many definitions of hash table, generally speaking, you can imagine hash table is an array, originally we access an element in array by using index, e.g. A[1], A[2]. However in hash table, we access element by the key,  e.g. A["Monday"], D["Marry"].  The great advantage of it is the speed to look up an element (O(1) time). 

How does Hash table works

Firstly, hash tables can be implemented based on many data structures, e.g. Linked list, array and linked list, binary search tree, etc. The idea is to store the <key, value> pair and build a way to access it. For better understanding, just consider an array, we put the <key, value> in a specific order. The way to locate the <key, value> using the key is called hashing. We can consider a hash function takes the key as the input, and output the location of the <key, value> in the array. A simple hash function is to used "mod" operation.  Use the "key mod array size" to get the hash, the index of the desired value. 

An example

Let's see a simple example.

We have a storage of  size 5:

idx      key       value

0         -1           0

1         -1           0

2         -1           0

3         -1           0

4         -1           0

key=-1 means the slot is empty.

The hash function is   hash(key) = key % 5;

First we insert <12, 12>  (first is key, second is value)

Compute the hash(12) = 2;

Store the <key, value> into the storage of idx 2.

idx      key       value

0         -1           0

1         -1           0

2         12          12

3         -1           0

4         -1           0

Next we insert <29,29>, hash(29)=4;

idx      key       value

0         -1           0

1         -1           0

2         12          12

3         -1           0

4         29          29

Then we insert <27,27>, where the hash code is 2. When we check the location 2, it is already in use. 

It is called a collision, where different key are mapped into same hash code. To deal with the collision, there are many methods, such as, chaining (use a linked list for each location), and rehashing (second function is used to map to another location). Usually we need to know at least these two kinds of methods.

Here we use the rehashing.  

The rehashing function is:  rehash(key) = (key+1)%5;

So, continue the above step, rehash(2) = 3; location 3 is empty, then store the <27,27> to location 3.

idx      key       value

0         -1           0

1         -1           0

2         12          12

3         27          27

4         29          29

If we further insert <32,32>, hash(32) = 2; location 2 is in use, rehash(2) = 3, location 3 is also in use,

Then rehash again, rehash(3) = 4, no available, rehash(4) = 0, OK! Store <32, 32 > in 0th slot.

idx      key       value

0         32          32

1         -1           0

2         12          12

3         27          27

4         29          29

That is the basic way of insert operation for a hash table.

To retrieve the value, e.g. we want to find the value of key <27, ?>, hash(27) = 2, check the key stored in location 2 , which is 12 !=27, then rehashing is need, rehash(2) = 3,  the key is 27, then return the value 27.

A simple implementation (in C++)

#include <iostream>


using namespace std;

const int sz = 5;

struct data{
 int id;
 int val;
};

class Hashtable{
 data dt[sz];
 int numel;
public:
 Hashtable();
 int hash(int &id);
 int rehash(int &id);
 int insert(data &d);
 int remove(data &d);
 int retrieve(int &id); 
 void output();
};


Hashtable::Hashtable(){
 for (int i=0;i<sz;i++){
   dt[i].id = -1;
dt[i].val = 0;
 }
 numel = 0;
}

int Hashtable::hash(int &id){
 return id%sz;
}

int Hashtable::rehash(int &id){
 return (id+1)%sz;
}

int Hashtable::insert(data &d){
 if (numel<sz){
   int hashid = hash(d.id);
if (hashid>=0 && hashid < sz){
 if (dt[hashid].id==-1 || dt[hashid].id==-2){
   dt[hashid].id = d.id;
   dt[hashid].val = d.val;
           numel++;
   return 0;
 }else{
   cout << "collision! rehashing..." <<endl;
   int i=0;
   while (i<sz){
     hashid = rehash(hashid);
 if (dt[hashid].id==-1 || dt[hashid].id==-2){
   dt[hashid].id = d.id;
   dt[hashid].val = d.val;
   numel++;
   return 0;
     }
 if (i==sz){return -1;}
 i++;
}
 }
}
 }else{return -1;}
}

int Hashtable::remove(data &d){
 int hashid = hash(d.id);
if (hashid>=0 && hashid < sz){
 if (dt[hashid].id==d.id){
   dt[hashid].id = -2;
   dt[hashid].val = 0;
   numel--;
   return 0;
 }else{
   int i=0;
   while (i<sz){
     hashid = rehash(hashid);
 if (dt[hashid].id==d.id){
   dt[hashid].id = -2;
   dt[hashid].val = 0;
   numel--;
   return 0;
     }
 if (i==sz){return -1;}
 i++;
}
 }
}
}

int Hashtable::retrieve(int &id){
 int hashid = hash(id);
 if (hashid>=0 && hashid < sz){
   if (dt[hashid].id==id){
 return dt[hashid].val;
}else{
  int i=0;
   while (i<sz){
     hashid = rehash(hashid);
 if (dt[hashid].id==id){
   return dt[hashid].val;
 }
 if (i==sz){return 0;}
 i++;
}
}
 }
}

void Hashtable::output(){
 cout << "idx  id  val" << endl;
 for (int i=0;i<sz;i++){
   cout << i << "    " << dt[i].id << "    " << dt[i].val << endl; 
 }
}


int main(){
 Hashtable hashtable;
 data d;
 d.id = 27;
 d.val = 27;
 hashtable.insert(d);
 hashtable.output();
 
 
 d.id = 99;
 d.val = 99;
 hashtable.insert(d);
 hashtable.output();
 
 d.id = 32;
 d.val = 32;
 hashtable.insert(d);
 hashtable.output();
 
 d.id = 77;
 d.val = 77;
 hashtable.insert(d);
 hashtable.output();
 
 //retrieve data
 int id = 77;
 int val = hashtable.retrieve(id);
 cout << endl;
 cout << "Retrieving ... " << endl;
 cout << "hashtable[" << id<< "]=" << val << endl;
 cout << endl;
 
 
 //delete element
 d.id = 32;
 d.val = 32;
 hashtable.remove(d);
 hashtable.output();
 
 d.id = 77;
 d.val = 77;
 hashtable.remove(d);
 hashtable.output();
 
     
 return 0;
}

 

leetcode Question 127: Word Ladder

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Analysis:
Use this problem to review the classic method : Bi-directional breadth first search.

Firstly, we targeting this specific problem. The idea is pretty straight forward:
From the start string, find the all the possible "next" string in the dictionary, and for each "next" string, find the "next next" strings, until meets the end string.

If there is a tree structure came up in your mind while you have seen this question for several mins, you almost get there!  Yes! At least this problem can be solved using the classical searching algorithm, Depth First Searching (DFS) and Breadth First Searching (BFS).

Which is better? The answer is  "it depends". But in this problem, from my personal perspective, the BFS is more reasonable since the problem requires a specific shortest path. Since BFS searches in a level-by-level way, it is more suitable to find the shortest path. And for this problem, both the start state (start string) and end state (end string) are known, it thus reminds me to try the double breadth first search!

What else should be considered?
At first, I'm doing it like this:    because I plan to use BFS, it is natural to find the valid string in the dictionary every time for the current top element in the queue, e.g. for i=1:dict_size { if valid(topstr, dict[i]), push();}. Does it work? Yes, there is no problem theoretically.  However, let's think a little deeper for this specific problem:   if we do the above loop, the complexity for this "add possible elements" is  O(m*n), m is the length of the string, n is the size of the dictionary. Can we do better?  Let's see the question again, where said that "only one letter can be changed", what does this mean? Of course it means we can check two strings from 1st to the last. Here is the trick when we saw the interface of the code------<unordered_set> . A nice property of unordered_set is it can find an element in O(1) time. The key here is:  the search for all valid strings in the dictionary can be considered as we generate all the possible strings and see if they are in the dictionary. For each char in the string, we can change it to the 26 letters, one position at a time, check if the new string exists in the dictionary. What is the complexity of this step?  O(m*26).

Actually I provide both code of the above idea, the 1st one can pass most of the test cases, but 3 failed 3 large cases. The 2nd one pass all the test cases. But the structure of the 1st one is more practical and general, I think it will help you more on the concept of BFS, as well as its extensions to other problems.

Double breadth first search.
When the start state and the aim state are all available for a search problem like this one, it is  a good very very very good chance to use the double breadth first search! How it works, if you got the idea of the BFS, it is not hard to understand---------Search from both direction!  Every time, we search one level from the start and one level from the end (there are also other schemes), the stop condition is found one node which has been marked by the other direction. A figure is show below which illustrates the idea and you can take a look at the code to get a better understanding of how it works.

Code (Cannot pass 3 of the large cases):

class Solution {
public:

    bool valid(string s1,string s2){
        bool flag=false;
        for (int i=0;i<s1.size();i++){
            if (s1[i]!=s2[i]){
                if (flag==true){return false;}
                else{flag=true;}
            }
        }
        return true;
    }

    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function  
        if (valid(start,end)){return 2;}
     
        if (dict.size()>2500){return 100;}
     
     
     
        struct node{
            string str;
            int lev;
            node(string s,int l):str(s),lev(l){}
        };
     
        queue<node>q;
        queue<node>rq;
        map<string,bool>mark;
        map<string,bool>rmark;
        for (auto it=dict.begin();it!=dict.end();it++){
            mark[*it]=false;
            rmark[*it]=false;
        }
         
        int level=1;
        int rlevel=1;
        q.push(node(start,1));
        rq.push(node(end,1));
     
        while (!q.empty() && !rq.empty()){
         
         
        if (q.size()<rq.size()){
            while (!q.empty() && q.front().lev==level){
                for (auto it=dict.begin();it!=dict.end();it++){
                    if (!mark[*it] && valid(q.front().str,*it)){
                        mark[*it]=true;
                        if (rmark[*it]){return q.front().lev+rq.back().lev;}
                        q.push(node(*it,level+1));
                    }
                }
                q.pop();
            }
            level++;
        }else{
     
            while (!rq.empty() && rq.front().lev==rlevel){
                for (auto it=dict.begin();it!=dict.end();it++){
                    if (!rmark[*it] && valid(*it,rq.front().str)){
                        rmark[*it]=true;
                        if (mark[*it]){return rq.front().lev+q.back().lev;}
                        rq.push(node(*it,rlevel+1));
                    }
                }
                rq.pop();
            }
         
            rlevel++;
        }
        }
     
        return 0;
    }
};

Code (Pass all the test cases):

class Solution {
public:
    
    vector<string> findDict(string str, unordered_set<string> &dict){
        vector<string> res;
        int sz = str.size();
        string s = str;
        for (int i=0;i<sz;i++){
            s = str;
            for (char j = 'a'; j<='z'; j++){
                s[i]=j;
                if (dict.find(s)!=dict.end()){
                    res.push_back(s);
                }
            }
            
        }
        return res;
    }
 bool valid(string s1,string s2){
        bool flag=false;
        for (int i=0;i<s1.size();i++){
            if (s1[i]!=s2[i]){
                if (flag==true){return false;}
                else{flag=true;}
            }
        }
        return true;
    }
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function  
        if (valid(start,end)){return 2;}
          
        
       struct node{  
            string str;
            int lev;
            node(string s,int l):str(s),lev(l){}
        };
       
        queue<node>q;
        queue<node>rq;
        map<string,bool>mark;
        map<string,bool>rmark;
        for (auto it=dict.begin();it!=dict.end();it++){
            mark[*it]=false;
            rmark[*it]=false;
        }
         
        int level=1;
        int rlevel=1;
        q.push(node(start,1));
        rq.push(node(end,1));
       
        while (!q.empty() && !rq.empty()){
           
           
        if (q.size()<rq.size()){
            while (!q.empty() && q.front().lev==level){
                
                vector<string> l = findDict(q.front().str,dict);
                for (auto it=l.begin();it!=l.end();it++){
                    if (!mark[*it]){
                        mark[*it]=true;
                        if (rmark[*it]){return q.front().lev+rq.back().lev;}
                        q.push(node(*it,level+1));
                    }
                }
                q.pop();
            }
            level++;
        }else{
       
            while (!rq.empty() && rq.front().lev==rlevel){
                
                vector<string> lr = findDict(rq.front().str,dict);
                for (auto it=lr.begin();it!=lr.end();it++){
                    if (!rmark[*it]){
                        rmark[*it]=true;
                        if (mark[*it]){return rq.front().lev+q.back().lev;}
                        rq.push(node(*it,rlevel+1));
                    }
                }
                rq.pop();
            }
           
            rlevel++;
        }
        }
       
        return 0;
    }
};

[Re-view] Recursive: Array Permutations

Intro

For the recursive function, it is very easy for most of us to write code for the fibonacci sequence. ( f(n)=f(n-1)+f(n-2) ). It seems we already got the idea of the recursion. What if you are asked to write the code for "8 queens problem" (actually this is also not hard at all) on a piece of paper? Some of you might feel  difficulty to rapidly and accurately do so. If you feel comfortable to write code for many recursive problem, you can definitely jump this post. But if you are easily confused facing slight complex recursive problems like me, maybe you wanna continue reading this post. From my experience, the 1st thing is to ask yourself, what are you thinking or what came out of you mind once you see a recursive problem? Recursion? Function argument list? Stop condition? for loop? Some lines of code?

Well, I'm neither good at remembering things, nor understanding things quickly. When I face the recursive problems, it's always a big mess! I just know this can be solved by recursion (and usually also DP, which is much harder), then I don't know what to do... So sad...

There is a saying that "Practice makes perfect" ! And "If you review the past, you will see new things!" In this post I will discuss the problem "Array permutation". I'll focus on the recursive procedure and present the way I remember the algorithm. Hopefully this will help you a little, but different people have different ways learning the same thing, try to find your own way, that is important.

Problem

Given an array of elements, return all the permutations.

e.g. Input: (1,2,3)

Return:  (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). 

Idea

First, we must make sure the problem can be solved using recursion. 

Usually, the problem which can be divided into sub problems is highly considered to be solvable using recursion.e.g. F(n)=F(n-1)+F(n-2). However, in this problem, it is not easy to see the sub problem. It may not work considering the length of the array, but it seems ok to consider each position. From the first element to the last... Every time I'm thinking of this, I have no way to go... 

Then I will remind myself about the recursion.  If the "function" e.g. f(n)=f(n-1)... cannot work, then I usually consider the following points:

1. Can I draw a Tree?
2. What are the stop/return conditions?
3. Does it need the backtracking?
4. Try to remember some standard code:
              func(){
                 if meet stop condition, return
                 else
                    for (i=1:n){
                        do something
                        func(next);
                        may need backtracking;
                    }
               }
      Despite this is not the master key solving the recursion, but it helps a lot when you have no idea at all.


If I can draw a tree, the problem is more straightforward and it related to the tree traversal problem, if you are familiar with that code, it would helps you a lot. If not, it is also easier to design the recursive function.

Stop/return condition is important. You have to think when your program will stop, when will it output the result. It is also the key to the recursion.

Backtracking is another issue when you do the "search", sometimes it is not needed, but sometimes you have to change back the status so that the search is not missing some branches. e.g., usually when there is loop in your recursion, be cautious!

For this problem, if you can draw a tree like this,  you are almost getting there! 

Then think about to construct the recursive function in your mind, see the tree and consider every node is a new function call:
Argument list: what we have to know in each recursion? The array and the length, the current position (a,n,k)
Stop condition: when all the positions are searched, print the output (if k==n)
Search rule:  swap current position with all the following positions (for i= k: n, swap)
Recursive:    fix current position, go to next position (perm(a, k+1,n))
Backtracking: needed! because there is a for loop, we swap the array before perm, so we swap back after.

Given these, writing code seems not hard then:

perm(int* A, int k, int n){
  if (k==n) {print(A); // print out the array, you can define by yourself}
  else{
    for (int i=k;i<n;i++){
      swap(A[i],A[k]); // swap the two values, you can define by yourself
      perm(A,k+1,n);
      swap(A[i],A[k]);
    }
  }
}

Some suggestions:

Please read the code carefully and according to the tree figure, you will find your own way understand that。
Please try to remember some classic recursive problems, don't have to remember every line of code, but the key lines or the structures of the function.
When you face a new problem, try to think the sub-problem, or the easy case (e.g. the number is 0 or 1).


I'll give more examples in the later posts.


(finished)