Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Solution:
1. find target row: O(m)
2. binary search that row: O(log n)
3. O(m+log n) time.
Improvement: treat it as an one dimensional array, and then use binary search

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowNum = findRow(matrix, target);
        if(rowNum >= matrix.length) return false;
        return binarySearch(matrix[rowNum], target, 0, matrix[0].length-1);
    }
    public Boolean binarySearch(int[] array, int target, int first, int last){
        if(first > last) return false;
        int mid = (first + last) / 2;
        if(array[mid] == target) return true;
        return (binarySearch(array, target, first, mid-1) || binarySearch(array, target, mid+1, last));
    }
    public int findRow(int[][] matrix, int target){
        int row = 0;
        while(!(target>=matrix[row][0] && target<=matrix[row][matrix[0].length-1])){
            row++;
            if(row >= matrix.length) break;
        }
        return row;
    }
}

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Solution:
Write out some text with different nRows on a piece of paper, then we can find out the relation between index and result row number.

public class Solution {
    public String convert(String s, int nRows) {
        int curRow = -1;
        
        // going down flag
        boolean flag = true;
        
        // its default value is "null"
        String[] strs = new String[nRows];
        Arrays.fill(strs, "");
        for(int i = 0; i < s.length(); i++){
            if(flag) 
                curRow++;
            // check a special case: ("AB", 1)
            else if (curRow > 0) 
                curRow--;
                
            if(curRow == nRows-1) 
                flag = false;
            else if(curRow == 0)
                flag = true;
                
            strs[curRow] += s.charAt(i);
        }
        
        // StringBuilder has better performance
        StringBuilder result = new StringBuilder();
        for(int i = 0; i < nRows; i++)
            result.append(strs[i]);
        return result.toString();
    }
}

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.

Solution:
Use DFS for each board position.

public class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        
        // to avoid duplicates
        boolean[][] visited = new boolean[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == word.charAt(0))
                    if(helper(board, word, 0, i, j, visited))
                        return true;
            }
        }
        return false;
    }
    
    public boolean helper(char[][] board, String word, int count, int i, int j, boolean[][] visited){
        if(count == word.length())
            return true;
        // out of boundary
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) 
            return false;
        if(visited[i][j] || board[i][j] != word.charAt(count))
            return false;
            
        visited[i][j] = true;
        
        if(helper(board, word, count+1, i-1, j, visited) || 
           helper(board, word, count+1, i+1, j, visited) ||
           helper(board, word, count+1, i, j-1, visited) ||
           helper(board, word, count+1, i, j+1, visited))
                return true;
        
        visited[i][j] = false;
        
        return false;
    }
}

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.

// bfs(queue) + dfs(HashMap> prevMap), 
 ///////////////////////////////////////////////////////////// 
///////// backtrack the paths is tricky /////////// 
//////////////////////////////////////////////////////////////

public class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();

        // build up a tree from breath first search.
        HashMap<String, Integer> level = new HashMap<String, Integer>();
        Queue<String> queue = new LinkedList<String>();

        // a word and all its parent nodes in the bfs tree.
        HashMap<String, HashSet<String>> prevMap = new HashMap<String, HashSet<String>>();
        
        if(start == null || end == null || start.length() != end.length()) return ret;
        
        queue.add(start);
        level.put(start,1);
        prevMap.put(start, new HashSet<String>());
        
        int minLen = Integer.MAX_VALUE;
        while(!queue.isEmpty()){
            String curStr = queue.poll();
            int curLevel = level.get(curStr);
            for(int i = 0; i < curStr.length(); i++){
                char[] c = curStr.toCharArray();
                for(char j = 'a'; j <= 'z'; j++){

                    // change one letter, and check if it is in the dict
                    c[i] = j;
                    String tmp = String.valueOf(c);
                    if(tmp.equals(curStr)) continue;
                    if(dict.contains(tmp) && (!level.containsKey(tmp) 
                                           || (level.containsKey(tmp) && level.get(tmp) > curLevel))){
                        
                        if(prevMap.containsKey(tmp)){
                            prevMap.get(tmp).add(curStr);
                        }
                        else{
                            prevMap.put(tmp, new HashSet<String>());
                            prevMap.get(tmp).add(curStr);
                            queue.add(tmp);
                            level.put(tmp, curLevel+1);
                        }        
                    }
                    
                    if(tmp.equals(end)){
                        // the first reaches here would have the shortest path length.
                        if(level.get(curStr) < minLen){
                            ArrayList<String> path = new ArrayList<String>();
                            path.add(end);   // start from the second last level!!! otherwise, we will get duplicates.
                            ret.addAll(traceback(curStr, prevMap, path));    // e.g. [hot,hog,dog],[hot,dot,dog]
                            minLen = curLevel+1;                             // if we start from dog, the result will be:
                        }                                                    //[hot,hog,dog], [hot,hog,dog],[hot,dot,dog]
                        else break;
                    }
                    
                }
            }
        }
        return ret;
    }
    // different from permutation
    public ArrayList<ArrayList<String>> traceback(String end, HashMap<String, HashSet<String>> prevMap, ArrayList<String> path){
        ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); 
        ArrayList<String> newPath = new ArrayList<String>(path);
        newPath.add(0, end);
        if(prevMap.get(end).size() == 0){
            result.add(newPath);
            return result;
        }
        for(String tmp : prevMap.get(end)){
            result.addAll(traceback(tmp, prevMap, newPath)); 
        }
        return result;
    }
    
}

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.

Solution:
BFS.

public class Solution {
    public int ladderLength(String start, String end, HashSet dict) {
        if(dict.size() == 0) return 0;
        return bfs(start, end, dict);
    }
    public int bfs(String start, String end, HashSet dict){
           Queue queue = new LinkedList();
           Queue len = new LinkedList();
           queue.add(start);
           len.add(1);
           while(!queue.isEmpty()){
               String word = queue.poll();
               int length = len.poll();
               if(word.equals(end)) return length;
               for(int i = 0; i < word.length(); i++){ // for each word, check each letter at each position
                   char[] c = word.toCharArray();
                   for(int j = 'a'; j <= 'z'; j++){
                       if(j == c[i]) continue;
                       c[i] = (char)(j);
                       String str = String.valueOf(c);
                       if(dict.contains(str)){
                           queue.add(str);
                           len.add(length+1);
                           dict.remove(str);
                       }
                   }
               }
           }
           return 0;
    }
}

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

Solution:
dfs + word break 1 = Time Limit Exceeded, died at "aaaaaaaaaaaaaaaaaaaaaaaaa..." 
improvement: only save routes, start from the end.

public class Solution {
    public ArrayList wordBreak(String s, Set dict) {
        ArrayList> dp = new ArrayList>();   
        for(int i = 0; i <= s.length(); i++){
            dp.add(new ArrayList());
        }
        ArrayList ret = new ArrayList();
        for(int i = 0; i < s.length(); i++){
            if(i > 0 && dp.get(i) == null) continue; // dp.get(i).size() == 0;
            for(String tmp : dict){
                int end = i + tmp.length();
                if(end > s.length()) continue;
                String str = s.substring(i, end);
                if(str.equals(tmp)){
                    dp.get(end).add(i);
                }
            }
        }
        StringBuilder strb = new StringBuilder();
        helper(s, dp, ret, strb, s.length(), 0);
        return ret;
    }
    public void helper(String s, ArrayList> dp, ArrayList ret, StringBuilder strb, int cur, int step){
        if(cur == 0){
            ret.add(strb.toString());
            return;
        }
        
        for(int i : dp.get(cur)){
            if(step > 0) strb.insert(0, " ");
            strb.insert(0, s.substring(i, cur));
            helper(s, dp, ret, strb, i, step + 1);
            strb.delete(0, cur-i);
            if(step > 0) strb.delete(0, 1);
        }
    }
}

Word Break

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

Solution:
first try: split s... 
second try: iterate dict & recursion -> Time Limit Exceeded 
third try: dp: dp[i] donates 0...i can be segmented. bottom-up. 

// bottom up!!!!!!!!!!!!!!!!!!!!!!
public class Solution {
    public boolean wordBreak(String s, Set dict) {
        int n = s.length();
        
        // dp[n] donates substring 0...n can be segmented or not
        boolean[] dp = new boolean[n];
        Arrays.fill(dp,false);
        
        for(int i = 0; i < n; i++){
            if(i > 0 && !dp[i-1])
                continue;
            for(String str : dict){
                int len = str.length();
                if ((i + len - 1) < n && s.substring(i,i+len).equals(str))
                    dp[i+len-1] = true;
            }    
        }
        
        return dp[n-1];
    }
}