Category Archives: DFS

Phone Screen @Uber Oct. 26th, 2015

Posted on by
Reply

Given a pattern and an input string, check if the input string matches the pattern.

Eg.
pattern: abab
input: howwhathowwhat
mapping: a => how, b => what
so match(abab, howwhathowwhat) -> true
match(abab, whathowhowwhat) -> false
match(“”, “”) -> true
match(“a”, “a”) -> true
match(“ab”, “abab”) -> true
match(“aaaa”, “howwhatwhathow”) -> false
match(“aaaa”, “whatwhatwhatwhat”) -> true

Each char in pattern string can match 1-n chars in input string. Same char can only match same string. Different chars can match same strings.

class Solution {
    public boolean match(String pattern, String input) {
        if (pattern == null || input == null || input.length() < pattern.length()) {
            return false;
        }
        Map<Character, String> map = new HashMap<>();
        return matchHelper(pattern, 0, input, 0, map);
    }

    public boolean matchHelper(String pattern, int index, String input, int inputIndex, Map<Character, String> map) {
        if (index == pattern.length()) {
            if (inputIndex == input.length()) {
                return true;
            }
            return false;
        }
        char c = pattern.charAt(index);

        if (map.containsKey(c)) {
            String val = map.get(c);
            if (inputIndex + val.length() <= input.length() && val.equals(input.substring(inputIndex, inputIndex + val.length()))) {
                return matchHelper(pattern, index + 1, input, inputIndex + val.length(), map);
            }
        } else {
            for (int i = inputIndex; i < input.length(); i++) {
                String val = input.substring(inputIndex, i + 1);
                map.put(c, val);
                if (matchHelper(pattern, index + 1, input, i + 1, map)) {
                    return true;
                }
                map.remove(c);
            }
        }
        return false;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.match("", "")); //true
        System.out.println(s.match("a", "a")); //true
        System.out.println(s.match("ab", "abab")); //true
        System.out.println(s.match("abab", "howwhathowwhat")); //true
        System.out.println(s.match("abab", "howwhatwhathow")); //false
        System.out.println(s.match("aaaa", "howwhatwhathow")); //false
        System.out.println(s.match("aaaa", "whatwhatwhatwhat")); //true
    }
}
FacebookTwitterGoogle+Share

Word Ladder I && II

Posted on by
Reply

Word Ladder I  — 只需要找一条最短路

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

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 – BFS模板 O(n*L) n: size of dict, L: the max length of the words

visited set记录已经访问过的路 一旦找到一条就退出

注意字符串的处理

public int ladderLength(String start, String end, Set<String> dict) {
    if (dict == null || dict.size() == 0) {
        return 0;
    }
    Queue<String> queue = new LinkedList<String>();
    queue.offer(start);
    int length = 1;
    Set<String> visited = new HashSet<>();
    visited.add(start);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String curr = queue.poll();
            for (char newChar = 'a'; newChar <= 'z'; newChar++) {
                for (int j = 0; j < start.length(); j++) {
                    if (newChar == curr.charAt(j)) {
                        continue;
                    }
                    String nextStep = curr.substring(0, j) + newChar + curr.substring(j + 1);
                    if (nextStep.equals(end)) {
                        return length + 1;
                    }
                    if (dict.contains(nextStep) && !visited.contains(nextStep)) {
                        queue.offer(nextStep);
                        visited.add(nextStep);
                    }
                }
            }
        }
        length++;
    }
    return 0;
}

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

Solution: BFS+DFS

1. 先用BFS找出最短路径的长度，同时把相邻节点和每个点到起点的distance保存下来

2. 用DFS找出所有最短路径，distance超过最短路径的长度的就不用考虑了，所谓pruning.

public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    List<List<String>> result = new ArrayList<>();
    if (dict == null || dict.size() == 0) {
        return result;
    }
    List<String> curr = new ArrayList<>();
    curr.add(start);
    Map<String, Integer> distance = new HashMap<>();
    Map<String, List<String>> neighborsMap = new HashMap<>();
    int minTrans = bfs(start, end, dict, distance, neighborsMap);
    findLaddersHelper(curr, end, minTrans, distance, neighborsMap, result);
    return result;
}

public void findLaddersHelper(List<String> curr, String end, int maxStep, Map<String, Integer> distance,
                              Map<String, List<String>> neighborsMap, List<List<String>> result) {
    String currStr = curr.get(curr.size() - 1);
    if (maxStep == 0) {
        if (currStr.equals(end)) {
            result.add(new ArrayList<>(curr));
        }
        return;
    }
    for (String neighbor : neighborsMap.get(currStr)) {
        if (distance.get(neighbor) == distance.get(currStr) + 1) {
            curr.add(neighbor);
            findLaddersHelper(curr, end, maxStep - 1, distance, neighborsMap, result);
            curr.remove(curr.size() - 1);
        }
    }
}

//first use BFS to find the shortest transformation
public int bfs(String start, String end, Set<String> dict,
               Map<String, Integer> distance, Map<String, List<String>> neighborsMap) {
    Queue<String> queue = new LinkedList<>();
    queue.offer(start);
    distance.put(start, 0);
    int minTrans = -1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        String str = queue.poll();
        List<String> neighbors = new ArrayList<>();
        for (char newChar = 'a'; newChar <= 'z'; newChar++) {
            for (int index = 0; index < start.length(); index++) {
                if (newChar == str.charAt(index)) {
                    continue;
                }
                String newStr = str.substring(0, index) + newChar + str.substring(index + 1);
                if (newStr.equals(end) && minTrans == -1) {
                    minTrans = distance.get(str) + 1;
                }
                if (dict.contains(newStr)) {
                    neighbors.add(newStr);
                    if (!distance.containsKey(newStr)) {
                        distance.put(newStr, distance.get(str) + 1);
                        queue.offer(newStr);
                    }
                }
            }
        }
        neighborsMap.put(str, neighbors);
    }
    return minTrans;
}

Combination Sum

Posted on by
Reply

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Example

given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Note

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
  • The solution set must not contain duplicate combinations.

Solution: Subsets 变种题 DFS

O(2^n) time

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    if (candidates == null) {
        return result;
    }
    Arrays.sort(candidates);
    combinationSumHelper(new ArrayList<Integer>(), 0, candidates, target, result);

    return result;
}

public void combinationSumHelper(ArrayList<Integer> curr, int index, int[] candidates, int target, List<List<Integer>> result) {
    if (target == 0) {
        result.add(new ArrayList<>(curr));
        return;
    }
    if (index >= candidates.length) {
        return;
    }
    for (int i = index; i < candidates.length; i++) {
        if (candidates[i] <= target) {
            curr.add(candidates[i]);
            combinationSumHelper(curr, i, candidates, target - candidates[i], result);
            curr.remove(curr.size() - 1);
        }
    }
}

Palindrome Partitioning

Posted on by
Reply

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.

Example

given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution: DFS, Subsets变种题 考虑每个间隙是partition还是不partition

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    partitionHelper(s, new ArrayList<String>(), result);
    return result;
}

public void partitionHelper(String s, ArrayList<String> curr, List<List<String>> result) {
    if (s.length() == 0) {
        result.add(new ArrayList<String>(curr));
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        String currString = s.substring(0, i + 1);
        if (isPalindrome(currString)) {
            curr.add(currString);
            partitionHelper(s.substring(i + 1), curr, result);
            curr.remove(curr.size() - 1); //important
        }
    }
}

public boolean isPalindrome(String s) {
    int start = 0;
    int end = s.length() - 1;
    while (start <= end) {
        if (s.charAt(start) != s.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

N-Queens I &&II

Posted on by
Reply

N-Queens I

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Example

There exist two distinct solutions to the 4-queens puzzle:

[

[“.Q..”, // Solution 1

“…Q”,

“Q…”,

“..Q.”],

[“..Q.”, // Solution 2

“Q…”,

“…Q”,

“.Q..”]

]

Solution1: Recursion DFS, Permutation模板，判断条件换一下

ArrayList<ArrayList<String>> solveNQueens(int n) {
    ArrayList<ArrayList<String>> result = new ArrayList<>();
    if (n <= 0) {
        return result;
    }
    int[][] chessBoard = new int[n][n];
    solveNQueensHelper(chessBoard, 0, result);
    return result;
}

//DFS
public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<ArrayList<String>> result) {
    if (row == chessBoard.length) {
        result.add(toStringList(chessBoard));
        return;
    }
    for (int col = 0; col < chessBoard[row].length; col++) {
        if (isValid(chessBoard, row, col)) {
            chessBoard[row][col] = 1;
            solveNQueensHelper(chessBoard, row + 1, result);
            chessBoard[row][col] = 0;
        }
    }
}

public boolean isValid(int[][] chessBoard, int row, int col) {
    for (int i = 1; i <= row; i++) {
        if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
                (col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
                chessBoard[row - i][col] == 1) {
            return false;
        }
    }
    return true;
}

public ArrayList<String> toStringList(int[][] chessBoard) {
    ArrayList<String> result = new ArrayList<>();
    for (int i = 0; i < chessBoard.length; i++) {
        StringBuilder row = new StringBuilder();
        for (int j = 0; j < chessBoard[i].length; j++) {
            if (chessBoard[i][j] == 0) {
                row.append('.');
            } else {
                row.append('Q');
            }
        }
        result.add(row.toString());
    }
    return result;
}

Solution 2. Non-Recursive

 

N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Example

For n=4, there are 2 distinct solutions.

Solution 1. Recursive. DFS

这里要注意的是 因为java的int和Integer类型都是传值不传reference，所以不能直接把int传进递归方法里，还是需要用一个链表, 或者用一个static variable

Solution 1. Recursive

public int totalNQueens(int n) {
    ArrayList<Integer> result = new ArrayList<>();
    if (n <= 0) {
        return 0;
    }
    int[][] chessBoard = new int[n][n];
    solveNQueensHelper(chessBoard, 0, result);
    return result.size();
}

public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<Integer> result) {
    if (row == chessBoard.length) {
        result.add(result.size() + 1);
        return;
    }
    for (int col = 0; col < chessBoard[row].length; col++) {
        if (isValid(chessBoard, row, col)) {
            chessBoard[row][col] = 1;
            solveNQueensHelper(chessBoard, row + 1, result);
            chessBoard[row][col] = 0;
        }
    }
}

public boolean isValid(int[][] chessBoard, int row, int col) {
    for (int i = 1; i <= row; i++) {
        if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
                (col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
                chessBoard[row - i][col] == 1) {
            return false;
        }
    }
    return true;
}

Solution 2. Non-Recursive

k Sum II

Posted on by
Reply

k Sum II

Given n unique integers, number k (1<=k<=n)  and target. Find all possible k integers where their sum is target.

Example

Given [1,2,3,4], k=2, target=5, [1,4] and [2,3] are possible solutions

Solutions: DFS

Time Complexity?

    public ArrayList < ArrayList < Integer >> kSumII(int A[], int k, int target) {
    	ArrayList < ArrayList < Integer >> result = new ArrayList < > ();
    	if (A == null) {
    		return result;
    	}
    	kSumIIHelper(new ArrayList < Integer > (), 0, A, k, target, result);
    	return result;
    }

    public void kSumIIHelper(ArrayList < Integer > curr, int index, int A[], int k,
    int target, ArrayList < ArrayList < Integer >> result) {
    	if (curr.size() == k) {
    		if (target == 0) {
    			result.add(new ArrayList < > (curr));
    		}
    		return;
    	}
    	for (int i = index; i < A.length; i++) {
    		curr.add(A[i]);
    		kSumIIHelper(curr, i + 1, A, k, target - A[i], result);
    		curr.remove(curr.size() - 1);
    	}
    }