Dynamic Programming

My understanding of dynamic programming is to store values to avoid recursion. This will improve the running time of an algorithm from exponential to linear.

Here's some excerpts I read from the book Algorithms in C++ : parts 1 - 4 : fundamentals : data structures : sorting : searching

1. Bottom-up DP:
    Instead of recursively call the functions and get the result Rn, we get Rn by computing all the function values in order starting at the smallest, using previously computed values at each step to compute the current value Rc.

2. Top-down DP:
    An even simpler view of the technique that allows us to execute recursive functions at the same cost as ( or less cost than) bottom-up DP in an automatic way.
    We instrument the recursive program to save each value that it computes (as its final action, ie at the next to last line of the recursive function ), and to check the saved values to avoid recomputing any of them (as its first action, ie, in the first line of the previously recursive function). It's also sometimes called memorization.

We can use bottom-up DP any time that we use the top-down DP, although we need to make sure that we compute the function values in an appropriate order, so that each value we need has been computed when we need it.

In top-down DP, we save known values. In bottom-up DP, we precompute them. We generally prefer top-down to bottom-up DP for:

1. It's a mechanical transformation of a natural problem solution. (Less code change)
2. The order of computing the subproblems takes care of itself
3. We may not need to compute answers to all the subproblems.

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"]
  ]

Initial attempt:
class Solution {
public:
    bool palindrome(string s)  
    {
        int len = s.size();
        for (int i=0;i<len/2; i++)
        {
            if (s[i]!=s[len-i])
              return false;
        }
        return true;
    }
   
    void helper( int i, string s, vector<string> &p, vector<vector<string>> &ret)
    {
        int slen = s.size();
        if (i==slen-1&&flag)
        {
            ret.push_back(p);
        }
       
   
        for (int k=i; k<slen; k++)
        {
            if (palindrome(s.substr(0,k)))
               {
                   p.push_back(s.substr(0,k));       //Got stuck
               }
        }
        i++;
    }
   
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ret;
        int len=s.size();
        if (len==0) return ret;
       
        vector<string> p;
        helper(0,s,p,ret);
        return ret;
    }
};

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

Idea:
Use BFS

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        int row = board.size();
        if (row<=1) return;
        int col = board[0].size();
        if (col<=1) return;
        for (int c=0; c<col; c=c+col-1)
        for (int r=0; r<row; r++)
         {
             if (board[r][c]=='O')
                findBdCoords(board,r, c, row, col);
         }
       
        for (int r=0; r<row; r=r+row-1)
        for (int c=0; c<col; c++)
        {
             if (board[r][c]=='O')
                findBdCoords(board,r, c, row, col);           
        }
        for (int r=0; r<row; r++)
        for (int c=0; c<col; c++)
        {
             if (board[r][c]=='O')
                   board[r][c]='X';
             if (board[r][c]=='B')
                 board[r][c]='O';
        }      
    }
    void findBdCoords(vector<vector<char>> &board, int r, int c, int row, int col)
    {
        if (board[r][c]!='B')
            board[r][c]='B';
        queue<pair<int,int>> q;
        q.push(make_pair(r,c));
       
        while(!q.empty())
        {
           //4 directions neighbor
           pair<int,int> cur = q.front();
           q.pop();
          
           r = cur.first, c = cur.second;
           pair<int, int> neis[4]={{r+1,c},{r-1,c},{r,c+1},{r,c-1}};
          
           for (int i=0; i<4; i++)
           {
               int rt = neis[i].first, ct = neis[i].second;
               if (rt>=0&&ct>=0&&rt<row&&ct<col&&board[rt][ct]=='O')
               {
                   q.push(make_pair(rt,ct));     
                    board[rt][ct]='B';               
               }
           }
        }
    }
};

Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) 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"]
Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

The solution is quite long and can be divided to several parts:


class Solution {
public:
void calAdj(const string s, unordered_set<string> & dict, unordered_set<string>& adjset){
     adjset.clear();
     for( int i = 0; i < s.size(); i++){
         string tmp(s);
         for( char az = 'a'; az <= 'z'; az++){
             tmp[i] = az;
             if( dict.find(tmp) != dict.end()){ //tmp is in dictionary
                 adjset.insert(tmp);
             }
         }
     }
}
void pathreverse(unordered_map<string, unordered_set<string>>& pathmap, string start, vector<vector<string>>& pathlist){
     vector<string> & lastpath = pathlist[pathlist.size()-1];
     lastpath.push_back( start );
     vector<string> prepath(lastpath);
     int p = 0;
     for( auto nstr : pathmap[start] ){
          if( p > 0 )//generate new path
              pathlist.push_back(prepath);
          pathreverse(pathmap, nstr, pathlist);
          p++;
     }
}
vector< vector<string> > findLadders(string start, string end, unordered_set<string> &dict){
      vector< vector<string> > pathlist;
      string tmp = start;
      start = end;
      end = tmp;
      int slen = start.size();
      int elen = end.size();
      if( slen != elen )
          return pathlist;
      dict.insert(start);
      dict.insert(end);
      //run bfs
      unordered_map<string, unordered_set<string>> pathmap;
      unordered_set<string> curset;
      curset.insert(start);
      dict.erase(start);
      unordered_set<string> adjset;
      bool find = false;
      while( !find && curset.size() > 0 ){
           unordered_set<string> preset(curset);
           curset.clear();
           for( auto pres : preset){
                if( pres == end ){//find it
                    find = true;
                    pathlist.push_back(vector<string>());
                    pathreverse(pathmap, end, pathlist);
                    break;
                }
                calAdj(pres, dict, adjset);
                curset.insert(adjset.begin(),adjset.end());//put in next layer
                for( auto nexts : adjset ){
                     pathmap[nexts].insert(pres); // record its parents
                }
           }
           for( auto vs : curset) // remove visited string
                dict.erase(vs);
      }
      return pathlist;
}
};

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.

Idea: Use BFS.
To do: make it more concise.
class Solution {
public:
  int ladderLength(string start, string end, unordered_set<string> &dict) {
   queue<string> curLevel;
   queue<string> nextLevel;
   string mid = start;
   bool find = false;
   string oStart = start;
   curLevel.push(start);
   int c = 1;
   while (!curLevel.empty() || !nextLevel.empty())
   {
    if (curLevel.empty())
    {
     curLevel.swap(nextLevel);
     c++;
    }
    start = curLevel.front();
    curLevel.pop();
    if (start == end)
    {
     find = true;
     break;
    }
    int n = start.size();
    for (int i = 0; i < n; i++)
    {
     for (int j = 0; j < 26; j++)
     {
      mid = start;
      if (start[i] != 'a' + j)
      {
       mid[i] = 'a' + j;
       if (dict.find(mid) != dict.end() || mid == end)  // To push the last element into the queue!
       {
        nextLevel.push(mid);
        if (dict.find(mid) != dict.end())
         dict.erase(mid); // we need to get rid of the visited word to avoid circles.
       }
       else
       {
        continue;
       }
      }
     }
    }
   }
   if (find)
    return c;
   else
    return 0;
  }
};

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

1. Backtracking:
My first answer was wrong and I started to realize I hadn't quite understood the essence of backtracking.

http://stackoverflow.com/questions/27069642/passing-parameter-recursion-c-letter-combinations-of-a-phone-number

class Solution {
public:
    const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
        "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
       
    vector<string> letterCombinations(string digits) {
      
        vector<string> res;
        string combo;
        bt( res, combo,digits);
        return res;
    }
   
  void bt(vector<string> &res, string combo, string digits)
  {
      int i=combo.size();
      int len =digits.size();
   if ( i == len)
   {
    res.push_back(combo);
   
    return;
   }
   int idx = digits[i] - '0';
   string tmp = keyboard[idx];
   int s = tmp.size();
   for (int j = 0; j<s; j++)
   {
    bt(res, combo + tmp[j], digits);
   }
  }
};

2. Iterative
 class Solution {
public:
    const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
        "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
       
    vector<string> letterCombinations(string digits) {
      
        vector<string> res(1, "");
        string combo;
       
        int n=digits.size();
        vector<string> tmp;
        for(int i=0; i<n; i++)
        {
            int m = keyboard[digits[i]-'0'].size();
            int rsize =res.size();
            for (int k=0; k<rsize; k++)
            {
                string ts = res[k];
                for (int j=0; j<m; j++)
                   {
                    res[k] = res[k] + keyboard[digits[i]-'0'][j];
                    tmp.push_back(res[k]);
                    res[k] = ts;
                   }
            }
            res = tmp;
            tmp.clear();
        }
        return res;
    }
};

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

For what permutations and combinations are, this is a good explanation:

http://betterexplained.com/articles/easy-permutations-and-combinations/

This problem has been asked on the internet a lot.
http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

Recursion and backtracking is a way to do it.

http://stackoverflow.com/questions/9552295/using-recursion-and-backtracking-to-generate-all-possible-combinations

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> res;
        if (n==0||k==0) return res;
        vector<int> path;
        bt(n, k, 1, 0, res, path);
        return res;
    }
   
    void bt(int n, int k, int start, int cur, vector<vector<int>> &r, vector<int> &p)
    {
        if (k==cur)
        {
            r.push_back(p);
            return;
        }
        else
        {
            for (int i=start; i<=n; i++)
            {
                p.push_back(i);
                bt(n,k,i+1,cur+1, r, p);
                p.pop_back();
            }
        }
    }
};

TO add iterative solution later.