Leetcode: Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Examples:

1. pattern = "abab", str = "redblueredblue" should return true.
2. pattern = "aaaa", str = "asdasdasdasd" should return true.
3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:
You may assume both pattern and str contains only lowercase letters.

Code (Java):

public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        if ((pattern == null || pattern.length() == 0) && (str == null || str.length() == 0)) {
            return true;
        }
        
        if ((pattern == null || pattern.length() == 0) || (str == null || str.length() == 0)) {
            return false;
        }
        
        Map<Character, String> forwardMap = new HashMap<>();
        Map<String, Character> invertedMap = new HashMap<>();
        
        return wordPatternMatchHelper(0, pattern, 0, str, forwardMap, invertedMap);
    }
    
    private boolean wordPatternMatchHelper(int pStart, String pattern, 
                                      int sStart, String str, 
                                      Map<Character, String> forwardMap, 
                                      Map<String, Character> invertedMap) {
        if (pStart == pattern.length() && sStart == str.length()) {
            return true;
        }
        
        if (pStart >= pattern.length() || sStart >= str.length()) {
            return false;
        }
        
        char pChar = pattern.charAt(pStart);
        for (int i = sStart; i < str.length(); i++) {
            String curr = str.substring(sStart, i + 1);
            
            if ((!forwardMap.containsKey(pChar)) && (!invertedMap.containsKey(curr))) {
                forwardMap.put(pChar, curr);
                invertedMap.put(curr, pChar);
                
                if (wordPatternMatchHelper(pStart + 1, pattern, i + 1, 
                        str, forwardMap, invertedMap)) {
                    return true;
                }
                
                forwardMap.remove(pChar);
                invertedMap.remove(curr);
            } else if (forwardMap.containsKey(pChar) && invertedMap.containsKey(curr)) {
                String dict = forwardMap.get(pChar);
                char pCharDict = invertedMap.get(curr);
                
                // IMPORTANT !! If not equal, instead of returnning false immedidately,
                // We need to try other longer substrings. 
                if (!dict.equals(curr) || pCharDict != pChar) {
                    continue;
                }
                
                if (wordPatternMatchHelper(pStart + 1, pattern, i + 1, str, 
                        forwardMap, invertedMap)) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

Leetcode: Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

Understand the problem:
It is very classic backtracking problem. We can start from each gate (0 point), and searching for its neighbors. We can either use DFS or BFS solution.

A DFS Solution:

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) {
            return;
        }
        
        int m = rooms.length;
        int n = rooms[0].length;
        
        boolean[][] visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    wallsAndGatesHelper(i, j, 0, visited, rooms);
                }
            }
        }
    }
    
    private void wallsAndGatesHelper(int row, int col, int distance, boolean[][] visited, int[][] rooms) {
        int rows = rooms.length;
        int cols = rooms[0].length;
        
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return;
        }
        
        // visited
        if (visited[row][col]) {
            return;
        }
        
        // Is wall?
        if (rooms[row][col] == -1) {
            return;
        }
        
        // Distance greater than current
        if (distance > rooms[row][col]) {
            return;
        }
        
        
        // Mark as visited
        visited[row][col] = true;
        
        if (distance < rooms[row][col]) {
            rooms[row][col] = distance;
        }
        
        // go up, down, left and right
        wallsAndGatesHelper(row - 1, col, distance + 1, visited, rooms);
        wallsAndGatesHelper(row + 1, col, distance + 1, visited, rooms);
        wallsAndGatesHelper(row, col - 1, distance + 1, visited, rooms);
        wallsAndGatesHelper(row, col + 1, distance + 1, visited, rooms);
        
        // Mark as unvisited
        visited[row][col] = false;
    }
}

A BFS Solution:

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) {
            return;
        }
        
        int m = rooms.length;
        int n = rooms[0].length;
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    wallsAndGatesHelper(i, j, 0, rooms, queue);
                }
            }
        }
    }
    
    private void wallsAndGatesHelper(int row, int col, int distance, int[][] rooms, Queue<Integer> queue) {
        fill(row, col, distance, rooms, queue);
        
        int m = rooms.length;
        int n = rooms[0].length;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cord = queue.poll();
                int x = cord / n;
                int y = cord % n;
            
                fill(x - 1, y, distance + 1, rooms, queue);
                fill(x + 1, y, distance + 1, rooms, queue);
                fill(x, y - 1, distance + 1, rooms, queue);
                fill(x, y + 1, distance + 1, rooms, queue);
            
            }
            distance++;
        }
    }
    
    private void fill (int row, int col, int distance, int[][] rooms, Queue<Integer> queue) {
        int m = rooms.length;
        int n = rooms[0].length;
        
        if (row < 0 || row >= m || col < 0 || col >= n) {
            return;
        }
        
        if (rooms[row][col] == -1) {
            return;
        }
        
        if (distance > rooms[row][col]) {
            return;
        }
        
        if (distance < rooms[row][col]) {
            rooms[row][col] = distance;
        }
        
        int cord = row * n + col;
        queue.offer(cord);
    }
}

Leetcode: Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

Hint:

1. If a palindromic permutation exists, we just need to generate the first half of the string.
2. To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.

Code (Java):

public class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return result;
        }
        
        // Step 1: determine if the string s is palindrome permutated
        Map<Character, Integer> map = new HashMap();
        if (!isPalindromePermutation(s, map)) {
            return result;
        }
        
        // Step 2: form the left half of the seed string
        StringBuffer sb = new StringBuffer();
        char middle = '\0';
        
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            char key = (char) pair.getKey();
            int val = (int) pair.getValue();
            while (val > 1) {
                sb.append(key);
                val -= 2;
            }
            
            if (val == 1) {
                middle = key;
            }
        }
        
        // Step 3: gnerate the permutations of the string
        permutation(sb.toString().toCharArray(), 0, result);
        List<String> result2 = new ArrayList<>();
        
        // Step 4: append the right half of the string
        for (String str : result) {
            StringBuffer tmp = new StringBuffer(str);
            if (middle != '\0') {
                tmp.append(middle);
            }
            
            for (int i = str.length() - 1; i >= 0; i--) {
                tmp.append(str.charAt(i));
            }
            result2.add(tmp.toString());
        }
        
        return result2;
    }
    
    private boolean isPalindromePermutation(String s, Map<Character, Integer> map) {
        int tolerance = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                int val = map.get(c);
                map.put(c, val + 1);
            } else {
                map.put(c, 1);
            }
        }
        
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            int val = (int) pair.getValue();
            if (val % 2 == 1) {
                tolerance++;
            }
        }
        
        if (tolerance <= 1) {
            return true;
        } else {
            return false;
        }
    }
    
    private void permutation(char[] s, int start, List<String> result) {
        if (start >= s.length) {
            result.add(new String(s));
            return;
        }
        
        for (int i = start; i < s.length; i++) {
            if (!containsDuplicate(s, start, i)) {
                swap(s, i, start);
                permutation(s, start + 1, result);
                swap(s, i, start);
            }
        }
    }
    
    private void swap(char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
    
    private boolean containsDuplicate(char[] s, int start, int end) {
        for (int i = start; i < end; i++) {
            if (s[i] == s[end]) {
                return true;
            }
        }
        
        return false;
    }
}