Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

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

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Naive Way: It's the same with  combination-sum . Just change the iteration index to index+1.

DFS iterative method

 public class Solution {  
   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Stack<SumNode> stack = new Stack<SumNode>();  
     Arrays.sort(num);  
     SumNode root = new SumNode(-1, 0, new ArrayList<Integer>());  
     stack.push(root);  
     while(!stack.isEmpty()){  
       SumNode node = stack.pop();  
       for(int i = node.index+1;i < num.length;i++){  
         if(node.sum + num[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(num[i]);  
         if(child.sum==target) set.add(child.path);  
         else stack.push(child);  
       }  
     }  
     rslt.addAll(set);  
     return rslt;  
   }  
 }  

BFS iterative method

 public class Solution {  
   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Queue<SumNode> queue = new LinkedList<SumNode>();  
     Arrays.sort(num);  
     SumNode root = new SumNode(-1, 0, new ArrayList<Integer>());  
     queue.add(root);  
     while(!queue.isEmpty()){  
       SumNode node = queue.poll();  
       for(int i = node.index+1;i < num.length;i++){  
         if(node.sum + num[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(num[i]);  
         if(child.sum==target) set.add(child.path);  
         else queue.add(child);  
       }  
     }  
     rslt.addAll(set);  
     return rslt;  
   }  
 }  

Recursive Method:

 public class Solution {  
   public List<List<Integer>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Arrays.sort(num);   
     dfs(num, -1, target, 0, new ArrayList<Integer>(), set);  
     rslt.addAll(set);  
     return rslt;   
   }  
   private void dfs(int[] n, int index, int target, int sum, List<Integer> path, Set<List<Integer>> set){   
    // ending case   
    if(sum==target){set.add(path); return;}   
    // recursion   
    for(int i = index+1;i < n.length;i++){   
     if(n[i]+sum > target) break;   
     List<Integer> list = new ArrayList<Integer>(path);   
     list.add(n[i]);   
     dfs(n, i, target, sum+n[i], list, set);   
    }   
   }   
 }  

Notice: Since all the above solution requires sorting at first. The time complexity is O(nlogn). Space is O(n!).

Improved Way: Can I apply iterative method without using extra class (SumNode in the above code).
If I directly use List<Integer> as nodes, I need to find a way to store the sum of the list and the current index.  I could use the first element to store the sum, the second element to store the current index.

 public class Solution {  
   public List<List<Integer>> combinationSum2(int[] num, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Set<List<Integer>> set = new HashSet<List<Integer>>();  
     Stack<List<Integer>> stack = new Stack<List<Integer>>();  
     Arrays.sort(num);  
     // initial list  
     List<Integer> root = new ArrayList<Integer>();  
     root.add(0);  
     root.add(-1);  
     // DFS  
     stack.push(root);  
     while(!stack.isEmpty()){  
       List<Integer> list = stack.pop();  
       // check if target found  
       if(list.get(0)==target){  
         List<Integer> path = new ArrayList<Integer>();  
         for(int i = 0;i < list.size()-2;i++)  
           path.add(list.get(i+2));  
         set.add(path);  
       }  
       // push child list  
       for(int i = list.get(1)+1;i < num.length;i++){  
         if(list.get(0)+num[i] > target) break;  
         List<Integer> path = new ArrayList<Integer>(list);  
         path.set(0, path.get(0)+num[i]);  
         path.set(1, i);  
         path.add(num[i]);  
         stack.push(path);  
       }  
     }  
     rslt.addAll(set);  
     return rslt;   
   }  
 }  

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

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

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

Naive Way: Make a recursive function to DFS on all possible combinations. And sort the entire array at first helps to keep numbers in order.

 public class Solution {  
   public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Arrays.sort(candidates);  
     dfs(candidates, 0, target, 0, new ArrayList<Integer>(), rslt);  
     return rslt;  
   }  
   private void dfs(int[] n, int index, int target, int sum, List<Integer> path, List<List<Integer>> rslt){  
     // ending case  
     if(sum==target){rslt.add(path); return;}  
     // recursion  
     for(int i = index;i < n.length;i++){  
       if(n[i]+sum > target) break;  
       List<Integer> list = new ArrayList<Integer>(path);  
       list.add(n[i]);  
       dfs(n, i, target, sum+n[i], list, rslt);  
     }  
   }  
 }  

The corresponding iterative way is using a stack to implement DFS.

 public class Solution {  
   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Stack<SumNode> stack = new Stack<SumNode>();  
     Arrays.sort(candidates);  
     SumNode root = new SumNode(0, 0, new ArrayList<Integer>());  
     stack.push(root);  
     while(!stack.isEmpty()){  
       SumNode node = stack.pop();  
       for(int i = node.index;i < candidates.length;i++){  
         if(node.sum + candidates[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(candidates[i]);  
         if(child.sum==target) rslt.add(child.path);  
         else stack.push(child);  
       }  
     }  
     return rslt;  
   }  
 }  

And I though about it for a while and tried BFS on it. (Just change the stack to queue). It works. DFS and BFS are two traversal methods on this problem.

 public class Solution {  
   class SumNode{  
     int index;  
     int sum;  
     List<Integer> path;  
     SumNode(int index, int value, List<Integer> path){  
       this.index = index;  
       this.sum = value;  
       this.path = new ArrayList<Integer>(path);  
     }  
     public void addNumber(int value){  
       this.sum += value;  
       this.path.add(value);  
     }  
   }  
   public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Queue<SumNode> queue = new LinkedList<SumNode>();  
     Arrays.sort(candidates);  
     SumNode root = new SumNode(0, 0, new ArrayList<Integer>());  
     queue.add(root);  
     while(!queue.isEmpty()){  
       SumNode node = queue.poll();  
       for(int i = node.index;i < candidates.length;i++){  
         if(node.sum + candidates[i] > target) break;  
         SumNode child = new SumNode(i, node.sum, node.path);  
         child.addNumber(candidates[i]);  
         if(child.sum==target) rslt.add(child.path);  
         else queue.add(child);  
       }  
     }  
     return rslt;  
   }  
 }  

Word Ladder II

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.

Naive Way:This question is hard. I tried at least 100 times but only get one of my solution passed the OJ in 1800+ms. Hard problem can always classify people, so I need to pay more attention to this question. In  word-ladder , I use a BFS approach, which is easy and quick to generate. What is different this time is that whether BFS or DFS, we need to mark each node that is visited. Consider this case:

start = 'red'
end = 'tax'
dict = ['ted', rad', 'tad']

since we cannot use a node twice, whether BFS or DFS will give us
either red->ted->tad->tax
or red->rad->tad->tax
because 'tad' is a common word in two paths.

A DFS with back-tracing is able to deal with that. But only DFS cannot ensure minimum steps. Thus, I apply level-order BFS first to put every word in a List<Set<String>> layer structure container, with the size of outer list equal to the minimum step. And apply DFS on this container to get each path. This is my first solution that get accepted. It takes 1400+ ms, while the average run time for this question is around 700ms.

 public class Solution {  
   public List<List<String>> findLadders(String start, String end, Set<String> dict) {  
     List<List<String>> rslt = new ArrayList<List<String>>();  
     List<Set<String>> tree = new ArrayList<Set<String>>();  
     boolean found = false;  
       
     // initialize first layer of the tree  
     Set<String> first_layer = new HashSet<String>();  
     first_layer.add(start);  
     if(dict.contains(start)) dict.remove(start);  
     tree.add(first_layer);  
       
     // add end to dictionary  
     dict.add(end);  
       
     // level-order traversal to construct the tree  
     while(!found && tree.get(tree.size()-1).size()!=0){  
       Set<String> new_layer = new HashSet<String>();  
       Set<String> cur_layer = tree.get(tree.size()-1);  
       Iterator<String> iter = cur_layer.iterator();  
       while(iter.hasNext()){  
         String s = iter.next();  
         char[] chars = s.toCharArray();  
         for(int j = 0;j < s.length();j++){  
           char original = chars[j];  
           for(char c = 'a';c <= 'z';c++){  
             chars[j] = c;  
             String t = new String(chars);  
             if(t.equals(end)) found = true;  
             if(dict.contains(t)){  
               if(!t.equals(end)) dict.remove(t);  
               new_layer.add(t);  
             }  
           }  
           chars[j] = original;  
         }  
       }  
       tree.add(new_layer);  
     }  
       
     // dfs to construct paths  
     Stack<String> path = new Stack<String>();  
     path.push(start);  
     dfs(start, end, 1, path, tree, rslt);  
       
     return rslt;  
   }  
     
   private void dfs(String s, String end, int index, Stack<String> path, List<Set<String>> tree, List<List<String>> rslt){  
     if(s.equals(end)){  
       List<String> validPath = new ArrayList<String>();  
       validPath.addAll(path);  
       rslt.add(validPath);  
       return;  
     }  
     if(index >= tree.size()) return;  
     Set<String> set = tree.get(index);  
     char[] chars = s.toCharArray();  
     for(int j = 0;j < s.length();j++){  
       char original = chars[j];  
       for(char c = 'a';c <= 'z';c++){  
         chars[j] = c;  
         String t = new String(chars);  
         if(set.contains(t)){  
           path.push(t);  
           dfs(t, end, index+1, path, tree, rslt);  
           path.pop();  
         }  
       }  
       chars[j] = original;  
     }  
   }  
 }  

Also, it is after several observation of others' code, I found that when listing the neighbors of a particular word, first convert it to char[] array and then replace a char instead of doing s.substring(0,i)+c+s.substring(i+1,s.length()) will save much time. It is probably because doing substring is initializing a new String each time, which is costly.

After seeing this post https://oj.leetcode.com/discuss/21902/java-solution-with-iteration on Discuss, I realized that DFS is not necessary. If I do a level-order traversal, delete the whole level from dict before traversal next level, I can efficiently deal with the case where a word is shared by to paths. Because a word shared by two paths must be at same location.

I give it a second trial using only BFS. And the code get accepted in 1000+ms.

 public class Solution {  
   public List<List<String>> findLadders(String start, String end, Set<String> dict) {  
     List<List<String>> rslt = new ArrayList<List<String>>();  
     Deque<List<String>> paths = new LinkedList<List<String>>();  
     boolean found = false;  
       
     // initialize path  
     List<String> path = new ArrayList<String>();  
     path.add(start);  
     paths.offerLast(path);  
       
     // add end to dictionary, remove start from dict  
     dict.add(end);  
     if(dict.contains(start)) dict.remove(start);  
       
     // BFS  
     while(!found && !paths.isEmpty()){  
       Set<String> set = new HashSet<String>();  
       int k = paths.size();  
       for(int i = 0;i < k;i++){  
         List<String> list = paths.pollFirst();  
         String s = list.get(list.size()-1);  
         for(String t : neighbors(s, dict)){  
           set.add(t);  
           List<String> newList = new ArrayList<String>(list);  
           newList.add(t);  
           paths.offerLast(newList);  
           if(t.equals(end)){  
             found = true;  
             rslt.add(newList);  
           }  
         }  
       }  
       dict.removeAll(set);  
     }  
     return rslt;  
   }  
     
   private List<String> neighbors(String s, Set<String> dict){  
     List<String> list = new ArrayList<String>();  
     char[] chars = s.toCharArray();  
     for(int j = 0;j < s.length();j++){  
       char original = chars[j];  
       for(char c = 'a';c <= 'z';c++){  
         chars[j] = c;  
         String t = new String(chars);  
         if(dict.contains(t)) list.add(t);  
       }  
       chars[j] = original;  
     }  
     return list;  
   }  
 }  

Improved Way: That is not enough. The highest run time distribution is around 700ms. I am far away from that yet. I looked into several posts about Word Ladder II. This two I found most helpful.
https://oj.leetcode.com/discuss/25970/java-modified-bfs-to-find-end-followed-dfs-reconstruct-paths
and http://yucoding.blogspot.com/2014/01/leetcode-question-word-ladder-ii.html (C++).

I found that the common point of their methods is to store the parents for each string instead of what is more straightforward, the children of each string. This reason for doing this is probably because storing the parents is using a lot less space than storing the children. (I tried storing children instead f parents, got MLE). Just Considering each word could have length * 26 at most children, while it will always have less than length*26 parents, since its neighbors selected  by its parent cannot become its parent.

To put it simple, parent selects children, only when two parents are alike, they can select same children. Thus, given each word, the size of its parents is much more less than the size of its children.

The following code applies mapping a word to its parents and got accept in 600+ ms. I keep the finding neighbor function and adding a dfs to find paths based on the parent relationship map.

 public class Solution {  
   public List<List<String>> findLadders(String start, String end, Set<String> dict) {  
     List<List<String>> rslt = new ArrayList<List<String>>();  
     Map<String, List<String>> parents = new HashMap<String, List<String>>();  
     boolean found = false;  
       
     // initialize  
     Set<String> cur_layer = new HashSet<String>();  
     cur_layer.add(start);  
     if(dict.contains(start)) dict.remove(start);  
     dict.add(end);  
       
     // BFS construct map  
     while(!found && !cur_layer.isEmpty()){  
       Set<String> new_layer = new HashSet<String>();  
       Iterator<String> iter = cur_layer.iterator();  
       while(iter.hasNext()){  
         String s = iter.next();  
         for(String t: neighbors(s, dict)){  
              new_layer.add(t);  
             if(!parents.containsKey(t)){  
               List<String> list = new ArrayList<String>();  
               list.add(s);  
               parents.put(t,list);  
             }else{  
               List<String> list = parents.get(t);  
               list.add(s);  
             }  
             if(t.equals(end)) found = true;  
         }  
       }  
       dict.removeAll(new_layer);  
       cur_layer = new_layer;  
     }  
       
     // DFS construct paths  
     Stack<String> path = new Stack<String>();  
     path.push(end);  
     dfs(start, end, path, parents, rslt);  
       
     return rslt;  
   }  
     
   private void dfs(String start, String s, Stack<String> path, Map<String, List<String>> parents, List<List<String>> rslt){  
        // base case  
     if(s.equals(start)){  
       List<String> list = new ArrayList<String>();  
       list.addAll(path);  
       Collections.reverse(list);  
       rslt.add(list);  
       return;  
     }  
     // edge case  
        if(!parents.containsKey(s)) return;  
     // recursion  
     for(String t: parents.get(s)){  
       path.push(t);  
       dfs(start, t, path, parents, rslt);  
       path.pop();  
     }  
   }  
     
   private List<String> neighbors(String s, Set<String> dict){   
     List<String> list = new ArrayList<String>();   
     char[] chars = s.toCharArray();   
     for(int j = 0;j < s.length();j++){   
       char original = chars[j];   
       for(char c = 'a';c <= 'z';c++){   
         chars[j] = c;   
         String t = new String(chars);   
         if(!t.equals(s) && dict.contains(t)) list.add(t);   
       }   
       chars[j] = original;   
     }   
     return list;   
   }   
 }