Leetcode: Word search (Backtracking )

PROBLEM:

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent"
cells are those horizontally or vertically neighboring. The same letter cell may not be used
more than once.

For example, Given board =

[

  ["ABCE"],

  ["SFCS"],

  ["ADEE"]

]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Hide Tags

 Array Backtracking

Show Similar Problems

Analysis:

This is a Backtracking problem. 

The critical part is how to design the backtracking for this case. The searching for the first capital in word should not be in the backtracking procedure, otherwise, it's difficult to implement it. We start to use backtracking from the second searching. 

The trivial thing here is the four possible candidates for each searching, namely the upper one, right one, lower one and the left one. 

Also, the boundary should be taken into consideration. 

In the same time, we need to maintain a flag for each character in the board to hold the information that whether it has been used or not. If the character has been used it can not be used again. Furthermore, if a branch of searching fails, we need to set the flag back for future use. 

It needs a lot of patience to correctly finish this problem. 

//////////////////////////////////////////////////////////////////////////////////////////////////////////

//codes 32ms

class Solution {

public:

       bool exist(vector<vector<char>>& board, string word) {

              if (board.size() == 0)return 0;

              //allocate a dynamic array (one dimention)

              int *flag = new int[board.size()*board[0].size()];

              memset(flag, 0, board.size()*board[0].size()*sizeof(int));//fill the memory,  0-not used; 1-used;

              //find the first match

              for (int i = 0; i < board.size(); i++){

                     for (int j = 0; j < board[0].size(); j++){

                           if (board[i][j] == word[0]){

                                  flag[i*board[0].size()+j] = 1;

                                  if (word.size() == 1)return true;

                                  if (judge(board, i, j, word, 1, flag))return true;    

                                  else flag[i*board[0].size() + j] = 0;

                           }

                     }

              }

              //delete new array

              delete[]flag;

              return false;

       }

       //checking the four adjacent neighbors

       bool judge(vector<vector<char>>& board, int i, int j, string word, int n, int*flag){

                  //check board[i-1,j]

              if (i - 1 >= 0 && board[i - 1][j] == word[n] && flag[(i-1)*board[0].size() + j] ==0){

                     flag[(i - 1)*board[0].size() + j] = 1;//set the related flag to 1

                           if (n==word.size()-1)return true;

                           else if(judge(board, i-1, j, word, n+1, flag)) return true;//tract back

                           else flag[(i - 1)*board[0].size() + j] = 0; //clear flag

                     }

                     //check board[i,j+1]

              if (j + 1 <= board[0].size() - 1 && board[i][j + 1] == word[n] && flag[i*board[0].size() + j+1] ==0){

                     flag[i*board[0].size() + j + 1] = 1;

                           if (n == word.size() - 1)return true;

                           else if (judge(board, i, j+1, word, n + 1, flag)) return true;

                           else flag[i*board[0].size() + j+1] = 0;

                     }

                     //check board[i+1,j]

              if (i + 1 <= board.size() - 1 && board[i + 1][j] == word[n] && flag[(i+1)*board[0].size() + j] == 0){

                           flag[(i+1)*board[0].size() + j] = 1;

                           if (n == word.size() - 1)return true;

                           else if (judge(board, i + 1, j, word, n + 1, flag)) return true;

                           else flag[(i + 1)*board[0].size() + j] = 0;

                     }

                     //check board[i,j-1]

              if (j - 1 >= 0 && board[i][j - 1] == word[n] && flag[i*board[0].size() + j - 1] ==0){

                     flag[i*board[0].size() + j - 1]=1;

                           if (n == word.size() - 1)return true;

                           else if (judge(board, i, j-1, word, n + 1, flag)) return true;

                           else flag[i*board[0].size() + j - 1]=0;

                     }

                     return false;

       }

};

////// Revised ///////////////////
A better method to 'remember' the used char in the board is to set them to some char like '+' or '.', and keep the original char with a single variable. 

///// 19ms////////////////////////
class Solution {
public:
    bool BT(vector<vector<char>>& board, int row, int col, string &word, int idx){
        if (idx==word.size()-1)return true;
        else{
            //left
            if(col-1>=0 && board[row][col-1]==word[idx+1]){
                char tmp=board[row][col-1];
                board[row][col-1]='.';//set as '.' to prevent matching
                if (BT(board, row, col-1, word, idx+1))return true;
                board[row][col-1]=tmp;
            }
            //right
            if(col+1<board[0].size() && board[row][col+1]==word[idx+1]){
                char tmp=board[row][col+1];
                board[row][col+1]='.';//set as '.' to prevent matching
                if (BT(board, row, col+1, word, idx+1))return true;
                board[row][col+1]=tmp;            
            }
            //up
            if(row-1>=0 && board[row-1][col]==word[idx+1]){
                char tmp=board[row-1][col];
                board[row-1][col]='.';//set as '.' to prevent matching
                if (BT(board, row-1, col, word, idx+1))return true;
                board[row-1][col]=tmp;
            }
            //down
            if(row+1<board.size() && board[row+1][col]==word[idx+1]){
                char tmp=board[row+1][col];
                board[row+1][col]='.';//set as '.' to prevent matching
                if (BT(board, row+1, col, word, idx+1))return true;
                board[row+1][col]=tmp;            
            }            
            
            return false;
        }
    }


    bool exist(vector<vector<char>>& board, string word) {
        for (int r=0;r<board.size();r++){
            for(int c=0;c<board[0].size();c++){
                if (board[r][c]==word[0]){
                    char tmp=board[r][c];
                    board[r][c]='.';
                    if(BT(board, r, c, word, 0))return true;
                    //else return false;
                    board[r][c]=tmp;
                }
            }
        }
        return false;
    }

};

Leetcode: Triangle (6ms)(Dynamic programming)

PROBLEM:
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[

     [2],

    [3,4],

   [6,5,7],

  [4,1,8,3]

]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Hide Tags

 Array Dynamic Programming

Analysis:

This is a classical DP problem. 

At first, you should understand the problem correctly: each step you may move to adjacent numbers on the row below. For each number, you have only two options in the next step. 

The first idea is using backtracking. Try all the possible path sum and chose the minimal one. There are two issues with this method. One is that it will use lots of stacks. The other one is that we don't know what the minimal value and we have to try all possible path to identify it (or we don't know what's the constrain to stop).  

The second idea is the DP to avoid the repeating works. See the figure below:

 the numbers in gray are triangle numbers while the black numbers are their possible sum. This figure says how the DP is implemented from top to down. To save previous calculation values, we use an array dp to store them and update them in the next round. For each number in the triangle, they may have two possible sum and we kill the bigger one and leave the smaller one. In the end, we use the smallest one in dp as the return value. 

A little bit better way to implement the DP is to sweep from down to top. But they are basic the same. 

////////////////////////////////////////////////////////////////////////////

//code (8ms)

class Solution {

public:

       int minimumTotal(vector<vector<int>>& triangle) {

              if (triangle.size() == 0)return 0;

              vector<int> dp, dp_tmp;

              dp.resize((triangle[triangle.size()-1].size()), 0);//defined to be the max length

              for (int i = 0; i < triangle.size(); i++){

                     dp_tmp.assign(dp.begin(),dp.end());

                     for (int j = 0; j < triangle[i].size(); j++){

                           if (j - 1 < 0){//triangle[i][j] is the left most item

                                  dp[j] = triangle[i][j] + dp_tmp[j];

                           }

                           else if (i == j){//triangle[i][j] is the right most item

                                  dp[j] = triangle[i][j] + dp_tmp[j - 1];

                           }

                           else{//triangle[i][j] is the middle

                                  dp[j] = triangle[i][j] + min(dp_tmp[j - 1], dp_tmp[j]);

                           }

                     }

              }

              //find the minimal value in dp

              int min_tmp=dp[0];

              for (int i = 0; i < dp.size(); i++){

                     if (min_tmp>dp[i]){

                           min_tmp = dp[i];

                     }

              }

              return min_tmp;

       }

};

Revised code for (6ms):
///////////////////////////////////////////////////

class Solution {

 public:

        int minimumTotal(vector<vector<int>>& triangle) {

               if (triangle.size() == 0) return 0;

               vector<int> dp1 = triangle[0];

               int row = triangle.size();

               for (int i = 1; i<row; i++){

                      vector<int> dp2;

                      dp2.assign(i + 1, 0);

                      for (int j = 0; j<i + 1; j++){

                            if (j == 0) dp2[j] = dp1[j] + triangle[i][j];

                            else if (j == i)dp2[j] = dp1[j - 1] + triangle[i][j];

                            else{

                                   int tmp1 = dp1[j] + triangle[i][j];

                                   int tmp2 = dp1[j - 1] + triangle[i][j];

                                   dp2[j] = tmp1 > tmp2 ? tmp2 : tmp1;

                            }

                      }

                      dp1 = dp2;

               }

               //find min

               sort(dp1.begin(), dp1.end());

               return dp1[0];

        }

 };