喜刷刷: depth first search

Showing posts with label depth first search. Show all posts

Tuesday, November 25, 2014

[LeetCode] Palindrome Partitioning I, II

Palindrome Partitioning I

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

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.

思路：Palindrome Partitioning I

遇到要求所有组合、可能、排列等解集的题目，一般都是用DFS + backtracking来做。要分割回文的前提是能够判断回文。在做DFS的时候，如果每次从start出发查找s[start:end]是否是回文，会使算法复杂度大大增加。而在Longest Palindromic Substring这题中已经知道如何用DP来计算任意s[i:j]是否是回文。因此可以先计算该判断矩阵，在DFS的时候用来剪枝，大大提高效率。

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<string>> ret;
        vector<string> sol;
        vector<vector<bool>> isPal(n, vector<bool>(n,false));
        for(int i=n-1; i>=0; i--) {
            for(int j=i; j<n; j++) {
                if((i+1>=j-1 || isPal[i+1][j-1]) && s[i]==s[j])
                    isPal[i][j] = true;
            }
        }
        findPartitions(s, 0, isPal, sol, ret);
        return ret; 
    }
    
    void findPartitions(string &s, int start, vector<vector<bool>> &isPal, vector<string> &sol, vector<vector<string>> &ret) {
        if(start==s.size()) {
            ret.push_back(sol);
            return;
        }
        
        for(int i=start; i<s.size(); i++) {
            if(isPal[start][i]) {
                int len = i-start+1;
                sol.push_back(s.substr(start, len));
                findPartitions(s, i+1, isPal, sol, ret);
                sol.pop_back();
            }
        }
    }
};

思路：Palindrome Partitioning II

整体的思路是一维DP。DP[i]表示长度为i的prefix：s[0: i-1]的min cut数量。
DP[i] = min (DP[j] + 1) ，对所有 0<=j<i，且s[j: i-1]为palindrome。
和I同样的技巧，用DP先计算存储一个palindrome判断矩阵isPal[i][j]，便于后面一维DP计算中能迅速判断s[j: i-1]是否为palindrome。

有一个更优的解法参考：
https://oj.leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        if(n<=1) return 0;
        vector<vector<bool>> isPal(n, vector<bool>(n, false));
        for(int i=n-1; i>=0; i--) {
            for(int j=i; j<n; j++) {
                if((i+1>j-1 || isPal[i+1][j-1]) && s[i]==s[j])
                    isPal[i][j] = true;
            }
        }
        
        vector<int> dp(n+1,INT_MAX);
        dp[0] = -1;
        for(int i=1; i<=n; i++) {
            for(int j=i-1; j>=0; j--) {
                if(isPal[j][i-1]) {
                    dp[i] = min(dp[i], dp[j]+1);
                }
            }
        }
        return dp[n];
    }
};

Monday, November 24, 2014

[LeetCode] 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

思路：

这题题意也略显含糊，实际上就是要将所有以O组成、但不连通到网格边缘的区域变为X。所以我们可以先在四边上寻找连通到边缘的区域，将它们的O都变成Y。剩余的所有O一定无法连通到边缘，所以可以全部变为X。最后再将所有Y变回O。

这题的测试比较tricky，上来没多想就用递归的DFS实现flood fill，结果发现run time error，栈溢出了：

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if(board.size()<3 || board[0].size()<3) return;
        fillBorders(board, 'O', 'Y');
        replace(board, 'O', 'X');
        fillBorders(board, 'Y', 'O');
    }
    
    void fill(vector<vector<char>> &board, int i, int j, char target, char c) {
        int m = board.size(), n = board[0].size();
        if(i<0 || j<0 || i>=m || j>=n || board[i][j]!=target) return;
        board[i][j] = c;
        fill(board, i-1, j, target, c);
        fill(board, i+1, j, target, c);
        fill(board, i, j-1, target, c);
        fill(board, i, j+1, target, c);
    }
    
    void fillBorders(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            if(board[i][0]==target) fill(board, i, 0, target, c);
            if(board[i][n-1]==target) fill(board, i, n-1, target, c);
        }
        
        for(int j=1; j<n-1; j++) {
            if(board[0][j]==target) fill(board, 0, j, target, c);
            if(board[m-1][j]==target) fill(board, m-1, j, target, c);
        }
    }
    
    
    void replace(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(board[i][j]==target)
                    board[i][j] = c;
            }
        }
    }
};

于是些了个迭代版的DFS，果然过了大数据测试。当然这里也可以用BFS实现flood fill。

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if(board.size()<3 || board[0].size()<3) return;
        fillBorders(board, 'O', 'Y');
        replace(board, 'O', 'X');
        fillBorders(board, 'Y', 'O');
    }
    
    void fill(vector<vector<char>> &board, int i, int j, char target, char c) {
        int m = board.size(), n = board[0].size();
        if(i<0 || j<0 || i>=m || j>=n || board[i][j]!=target) return;
        stack<pair<int,int>> s;
        s.push(make_pair(i,j));
        
        while(!s.empty()) {
            i = s.top().first;
            j = s.top().second;
            s.pop();
            board[i][j] = c;
            if(i>0 && board[i-1][j]==target) s.push(make_pair(i-1,j));
            if(i<m-1 && board[i+1][j]==target) s.push(make_pair(i+1,j));
            if(j>0 && board[i][j-1]==target) s.push(make_pair(i,j-1));
            if(j<n-1 && board[i][j+1]==target) s.push(make_pair(i,j+1));
        }
    }
    
    void fillBorders(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            if(board[i][0]==target) fill(board, i, 0, target, c);
            if(board[i][n-1]==target) fill(board, i, n-1, target, c);
        }
        
        for(int j=1; j<n-1; j++) {
            if(board[0][j]==target) fill(board, 0, j, target, c);
            if(board[m-1][j]==target) fill(board, m-1, j, target, c);
        }
    }
    
    
    void replace(vector<vector<char>> &board, char target, char c) {
        int m = board.size(), n = board[0].size();
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(board[i][j]==target)
                    board[i][j] = c;
            }
        }
    }
};

Sunday, November 23, 2014

[LeetCode] Word Break I, II

Word Break I

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

思路：Word Break I

看到这题第一反应是DFS枚举查找，直到“探”到string尾部则算成功。但题目并不要求给出是如何break的，而只要判断是否能break。对这类判断“是”与“否”的可以用DFS暴力解决的题，可以尝试用DP做book keeping中间判断状态，避免DFS的反复搜索。比如这题，可以用一个数组dp记录S[0:i]是否能break。

dp[i]：S[0:i-1]是否能被break。例如dp[1]表示s[0]是否能被break。

dp[0] = true

dp[i] = true if and only if:

1. 存在一个i-1>=k>=0，使s[k:i-1]存在于dict中。

2. s[0: k-1]可以被break，即dp[k] = true。

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        vector<bool> dp(s.size()+1,false);
        dp[0] = true;
        for(int i=0; i<s.size(); i++) {
            for(int j=i; j>=0; j--) {
                if(dp[j] && dict.count(s.substr(j,i-j+1))!=0) {
                    dp[i+1] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

思路：Word Break II

要求所有word break的可能，自然想到的是用DFS来做。但是发现居然过不了大集合，代码如下：

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> sentences;
        vector<string> sol;
        findWordBreak(s, dict, 0, sol, sentences);
        return sentences;
    }
    
    void findWordBreak(string &s, unordered_set<string> &dict, int start, vector<string> &sol, vector<string> &sentences) {
        if(start==s.size() && !sol.empty()) {   // find word break
            string temp = sol[0];
            for(int i=1; i<sol.size(); i++) 
                temp.append(" "+sol[i]);
            sentences.push_back(temp);
        }
        
        string word;
        for(int i=start; i<s.size(); i++) {
            word.push_back(s[i]);
            if(dict.count(word)!=0) {
                sol.push_back(word);
                findWordBreak(s, dict, i+1, sol, sentences);
                sol.pop_back();
            }
        }
    }
};

分析：

要求所有可能的word break的解集，DFS是跑不了的。所以问题的关键在于如何剪枝。

Tuesday, November 18, 2014

[LeetCode] Word Search

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.

思路：

以board上的每个cell为出发点，利用depth first search向上下左右四个方向搜索匹配word。搜索的时候要考虑board的边界，cell是否已经在DFS的路径上被用过，以及cell上的值是否与word的当前字符匹配。为了跟踪DFS的路径避免同一个cell被访问多次，使用一个visited矩阵来代表board上任意的cell(i, j)是否已经被访问过。

class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        if(board.empty() || board[0].empty()) return false;
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(),false));
        for(int i=0; i<board.size(); i++) {
            for(int j=0; j<board[i].size(); j++) {
                if(findWord(board, visited, i, j, word, 0)) return true;
            }
        }
        return false;
    }
    
    bool findWord(vector<vector<char>> &board, vector<vector<bool>> &visited, int row, int col, string &word, int index) {
        if(index==word.size()) return true;
        if(row<0 || col<0 || row>=board.size() || col>=board[0].size() || visited[row][col] || board[row][col]!=word[index]) 
            return false;
            
        visited[row][col] = true;
        if(findWord(board, visited, row-1, col, word, index+1)) return true;  
        if(findWord(board, visited, row+1, col, word, index+1)) return true;
        if(findWord(board, visited, row, col-1, word, index+1)) return true;
        if(findWord(board, visited, row, col+1, word, index+1)) return true;
        visited[row][col] = false;
        return false;
    }
};

总结：

ln 16是这题最关键的点，包括了3个判断：

(1) 当前坐标是否在board内

(2) 当前cell是否已经在本次DFS路径上已经被访问

(3) 当前cell是否匹配当前word中的字符。