House Robber II

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Refer from House Robber I
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

My Thinkings:

The only difference is it's a circle now instead of a straight line. The last one cant be robbed if the first one has been robbed. If I am going to use the same Dynamic Programming Process, maintaining an array to store current optimized robbery status, I can tell if the first house has been robbed or not from if(opt[1] == 0). However, I cant control the robber not to rob house 1 since opt[1] will always equal to the value in the first house.

That seems to stop me from considering it a DP process. Then I came up with a more mathematics thought-- each time spin the house value by one step, calling DP solution on each new array. Now, I realize how stupid I am. In this way, I still didn't solve the circling thing-- how to include both cases, with the first robbed and with the first one save. And since every house is in a circle, it really doesn't matter where is the starting point if your algorithm is a correct one.

Then I turned to DFS. Since a lot of DP problem can be rewrote in a cached DFS(memorized DFS). It took me some time and finally I gave up this idea since I dont know what to cache.

The final result is easy. It is always like that. I realize I just need to change the initial condition and  run DP twice.

 public class Solution {  
   public int rob(int[] nums) {  
     return Math.max(circle_rob(nums, true), circle_rob(nums, false));  
   }  
     
   private int circle_rob(int[] nums, boolean robFirst){  
     // edge case  
     if(nums == null || nums.length == 0) return 0;  
       
     int[] opt = new int[nums.length+1];  
       
     // initial condition  
     opt[0] = 0;  
     opt[1] = robFirst?nums[0]:0;  
       
     // iteration  
     for(int i = 2;i < opt.length;i++){  
       if(i!=opt.length-1){   
         // normal case  
         opt[i] = Math.max(opt[i-2] + nums[i-1], opt[i-1]);  
       }else{  
         // last robbery  
         opt[i] = robFirst?opt[i-1]:Math.max(opt[i-2]+nums[i-1],opt[i-1]);  
       }  
     }  
       
     return opt[opt.length-1];  
   
   }  
     
     
 }  

Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true 

Naive Thinking: Similar to Implement Trie(prefix-tree) . But pattern '.' was included. For addWord() method, '.' doesn't affect the process since its not necessary to combine '.ad' and 'bad'. It's okay to leave both in the tree. While for search() method, when '.' appear in the word, we need to search all child nodes. when '.' appear in the node, we need to search this node also. So I apply a DFS approach to do search().

 public class WordDictionary {  
     
   LetterNode head = new LetterNode('*');  
   
   // Adds a word into the data structure.  
   public void addWord(String word) {  
     LetterNode cur = head;  
     for(int i = 0;i < word.length();i++){  
       if(cur.next.containsKey(word.charAt(i))){  
         cur = cur.next.get(word.charAt(i));  
       }else{  
         LetterNode son = new LetterNode(word.charAt(i));  
         cur.next.put(word.charAt(i), son);  
         cur = son;  
       }  
     }  
     cur.isEnd = true;  
   }  
   
   // Returns if the word is in the data structure. A word could  
   // contain the dot character '.' to represent any one letter.  
   public boolean search(String word) {  
     // DFS  
     return search(head, word, 0);  
   }  
     
   private boolean search(LetterNode node, String word, int layer){  
     LetterNode son = null, dot = null;  
     // ending case  
     if(node == null) return false;  
     if(layer == word.length()) return node.isEnd;  
       
     // general case  
     if(word.charAt(layer)=='.'){   
       // Go though all next nodes when '.' appear  
       Iterator iter = node.next.entrySet().iterator();  
       while(iter.hasNext()){  
         Map.Entry pair = (Map.Entry)iter.next();  
         if(search((LetterNode)pair.getValue(), word, layer+1))  
           return true;  
       }  
     }else{  
       // Go though target character nodes and '.' nodes  
       if(node.next.containsKey(word.charAt(layer)))  
         son = node.next.get(word.charAt(layer));  
       if(node.next.containsKey('.'))  
         dot = node.next.get('.');  
       if(son!=null || dot!=null)  
         return search(son, word, layer+1) || search(dot, word, layer+1);  
     }  
         
     return false;  
   }  
     
   class LetterNode{  
     Map<Character, LetterNode> next;  
     char letter;  
     boolean isEnd;  
     LetterNode(char c){  
       this.letter = c;  
       this.next = new HashMap<Character, LetterNode>();  
       this.isEnd = false;  
     }  
   }  
 }  
   
 // Your WordDictionary object will be instantiated and called as such:  
 // WordDictionary wordDictionary = new WordDictionary();  
 // wordDictionary.addWord("word");  
 // wordDictionary.search("pattern");  

Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].


Naive Thinking: Everything the same with Course Schedule I . Return the order of topological sort instead of whether can it be passed. Use an arraylist to store the order first. And then check if the size meets the number of courses. Then copy the arraylist to output array.

 public class Solution {  
   public int[] findOrder(int numCourses, int[][] prerequisites) {  
       
     // initilization  
     int[] rslt = new int[0];  
     List<Integer> order = new ArrayList<Integer>();  
     Queue<Integer> zero_pre_courses = new LinkedList<Integer>();  
     List<Course> courses = new ArrayList<Course>();  
     for(int i = 0;i < numCourses;i++) courses.add(new Course(i));  
       
     // read in prerequisite infomation  
     for(int i = 0;i < prerequisites.length;i++){  
       courses.get(prerequisites[i][0]).prerequisite.add(prerequisites[i][1]);  
       courses.get(prerequisites[i][1]).advanced.add(prerequisites[i][0]);  
     }  
       
     // group zero_prerequisite courses  
     for(int i = 0;i < numCourses;i++)  
       if(courses.get(i).prerequisite.isEmpty()) zero_pre_courses.add(i);  
       
     // topological sort  
     while(!zero_pre_courses.isEmpty()){  
       int curNum = zero_pre_courses.poll();  
       order.add(curNum);  
       Iterator<Integer> iter = courses.get(curNum).advanced.iterator();  
       while(iter.hasNext()){  
         int advNum = iter.next();  
         courses.get(advNum).prerequisite.remove(curNum);  
         if(courses.get(advNum).prerequisite.isEmpty()) zero_pre_courses.add(advNum);  
       }  
     }  
       
     // generate result  
     if(order.size() == numCourses){  
       rslt = new int[numCourses];  
       for(int i = 0;i < numCourses;i++)  
         rslt[i] = order.get(i);  
     }  
       
     return rslt;  
   }  
     
   class Course{  
     Set<Integer> prerequisite;  
     Set<Integer> advanced;  
     int label;  
     Course(int l){  
       this.label = l;  
       this.prerequisite = new HashSet<Integer>();  
       this.advanced = new HashSet<Integer>();  
     }  
   }  
 }