Sunday, April 10, 2016

LeetCode 132 - Palindrome Partitioning II


Related: Leetcode 131 - Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
X. O(n) space
https://discuss.leetcode.com/topic/2840/my-solution-does-not-need-a-table-for-palindrome-is-it-right-it-uses-only-o-n-space/12
  public int minCut(String s) {
        if(s.length()==0)return 0;
        int[]c=new int[s.length()+1];
        for(int i=0;i<s.length();i++)c[i]=Integer.MAX_VALUE;
        c[s.length()]=-1;
        for(int i=s.length()-1;i>=0;i--){
            for(int a=i,b=i;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a--,b++) c[a]=Math.min(c[a],1+c[b+1]);
            for(int a=i,b=i+1;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a--,b++) c[a]=Math.min(c[a],1+c[b+1]);
        }
        return c[0];
    }
https://github.com/liguangsheng/leetcode/blob/master/132-Palindrome-Partitioning-II.MD
使用一个数组cut来记录回文串的分组,一个字符串最多可以分为每个字符一组,也就是n组(n为字符串长度)。初始化cut为1...n。
遍历每个字符作为中心,然后偏移量offset逐渐增加,判断中心两侧offset的字符是否相等,来判断是否回文。
这里注意回文有两种,一种形如"abcba"的奇数串,一种形如"abba"的偶数串,要分别处理。
当某个字符作为中心时,当前回文串的低位的前一位记录的是前一组的组别,+1之后得到当前回文串的组别,用+1之后的值和其本身的值比较,然后将较小值写入高位,使高位记录当前回文串的组别。
动态更新cut数组,最终可推导出最后一个分组,最后一个分组的组别号-1就是分割次数。
int minCut(char *s) {
    int len = strlen(s);
    int cut[len + 1];
    for(int i = 0; i <= len; i++) cut[i] = i;
    for(int center = 0; center < len; center++) {
        for(int offset = 0; center - offset >= 0 && center + offset < len
              && s[center - offset] == s[center + offset]; offset++)
            cut[center + offset + 1] = MIN(cut[center + offset + 1], cut[center - offset] + 1);
        for(int offset = 0; center - offset - 1 >= 0 && center + offset < len
              && s[center - offset - 1] == s[center + offset]; offset++)
            cut[center + offset + 1] = MIN(cut[center + offset + 1], cut[center - offset - 1] + 1);
    }
    return cut[len] - 1;
}

X. DP - Compute isPalindrom[][] and cuts[] at same time
Use DP. dp[i][j] store if s[i..j] is palindrome or not. res[j] is the min cut of s[0..j]. In the loop, keep update dp[i][j] matrix and res[j] array. The complexity is O(N^2).
   public int minCut(String s) {  
     int n=s.length();  
     char[] c=s.toCharArray();  
     boolean[][] dp=new boolean[n][n];  
     int[] res=new int[n];  
     for (int j=0; j<n; j++) {  
       res[j]=Integer.MAX_VALUE;  
       for (int i=j; i>=0; i--) {  
         dp[i][j]=i==j || (c[i]==c[j] && (i+1>=j-1 || dp[i+1][j-1]));  
         if (dp[i][j]) {  
           int cut=(i==0)?0:res[i-1]+1;  
           res[j]=Math.min(res[j],cut);  
         }  
       }  
     }  
     return res[n-1];  
   }  
public int minCut(String s) {
    int n = s.length();
 
 boolean dp[][] = new boolean[n][n];
 int cut[] = new int[n];
 
 for (int j = 0; j < n; j++) {
  cut[j] = j; //set maximum # of cut
  for (int i = 0; i <= j; i++) {
   if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i+1][j-1])) {
    dp[i][j] = true;
 
    // if need to cut, add 1 to the previous cut[i-1]
    if (i > 0){
     cut[j] = Math.min(cut[j], cut[i-1] + 1);
    }else{
    // if [0...j] is palindrome, no need to cut    
     cut[j] = 0; 
    } 
   }
  }
 }
 
 return cut[n-1];
}

  1. pal[i][j] , which is whether s[i..j] forms a pal
  2. d[i], which is the minCut for s[i..n-1]
Once we comes to a pal[i][j]==true:
  • if j==n-1, the string s[i..n-1] is a Pal, minCut is 0, d[i]=0;
  • else: the current cut num (first cut s[i..j] and then cut the rest s[j+1...n-1]) is 1+d[j+1], compare it to the exisiting minCut num d[i], repalce if smaller.
d[0] is the answer.
int minCut(string s) { if(s.empty()) return 0; int n = s.size(); vector<vector<bool>> pal(n,vector<bool>(n,false)); vector<int> d(n); for(int i=n-1;i>=0;i--) { d[i]=n-i-1; for(int j=i;j<n;j++) { if(s[i]==s[j] && (j-i<2 || pal[i+1][j-1])) { pal[i][j]=true; if(j==n-1) d[i]=0; else if(d[j+1]+1<d[i]) d[i]=d[j+1]+1; } } } return d[0]; }
X. DP - Compute isPalindrom[][] then cuts[]
    public int minCut(String s) 
    {
        if(s == null || s.isEmpty())  
            return 0;
        // Building a dict
        boolean[][] dict = buildDict(s);
         
        // result[i] means from s[0,i], the min cut
        int[] result = new int[s.length() + 1];
        result[0] = 0;
        for (int i = 0 ; i < s.length() ; i ++)
        {
            result[i + 1] = i + 1// max cut: single char cut
            for (int j = 0 ; j <= i ; j ++)
            {
                if (dict[j][i])
                {
                    result[i + 1] = Math.min(result[i + 1], result[j] + 1);
                }
            }
        }
         
        return result[result.length - 1] - 1;
    }
     
    // dict[i][j] means substring(i, j + 1) is palin
    // dict(i, j) = char[i] == char[j] && dict(i + 1, j - 1)
    // So i starts from s.length to 0
    // j starts from i to s.length
    private boolean[][] buildDict(String s)
    {
        int len = s.length();
        boolean[][] dict = new boolean[len][len];
         
        for (int i = len - 1 ; i >= 0 ; i --)
        {
            for (int j = i ; j < len ; j ++)
            {
                if (i == j)
                    dict[i][j] = true;
                else if(i + 1 == j)
                    dict[i][j] = s.charAt(i) == s.charAt(j);
                else
                    dict[i][j] = s.charAt(i) == s.charAt(j) && dict[i + 1][j - 1];
            }
        }
        return dict;
    }
http://bangbingsyb.blogspot.com/2014/11/leetcode-palindrome-partitioning-i-ii.html
http://yucoding.blogspot.com/2013/08/leetcode-question-133-palindrome.html

X.https://leetcode.com/discuss/31828/my-accepted-java-solution
So my thought process was go through the string, char by char starting from the left. The current character would be the center of the palindrome and expand as much as I can. After it ceases to be a palindrome (e.g no longer matching end chars or reached the boundary of the string), the cost would be "1 + the cost of the substring I already processed to the left of the current palindrome I am on". I compare this cost under the index of the last char of my current palindrome. If it is less than what was previously recorded, the I record this new cost.
For example, let's take 'abb':
  • Start with 'a'. Obviously a cost of 0 (base case)
  • Now we go to 'b' (index 1). Since we haven't visited 'b', let's assign an initial cost to it, which is 1 + cost[0]. So cost[1] = 0+1 = 1. This makes sense since you only need a 1 cut to get two palindromes: 'a' and 'b'
  • Let's try to expand 'b'
    • 'ab': It's not a palindrome so do nothing
    • 'abb': Not a palindrome either
  • After expansion, cost[1] remains 1.
  • Now we go to 'b' (index 2). Initial cost[2] = cost[1]+1 = 2. Expanding...
    • 'bb': Hey, a palindrome! So I will compute a cost of cost[0]+1 = 1 (remember "1 + cost of substring to the left...). Is 1 less than what I initially have in cost[2]? Yup, it is. So I record it: cost[2] = 1
  • After expansion, cost[2] was changed from 2 to 1, and rightfully so because that is the minimum cut we can do to get all substrings as palindromes: 'a' and 'bb'.
Another example but we'll go faster this time: 'xccx'
  • 'x': cost[0] = 0. Base case.
  • 'c' (index 1): Init cost[1] = 1. Expanding...
    • 'xc': Nope
    • 'xcc': Nope
  • 'c': Init cost[2] = 2. Expanding...
    • 'cc->xccx': Yes. Since we reached start of string, this is a base case. So new cost = 0. Is 0 > cost[3] = Integer.MAX_VALUE? Yes, so cost[3] = 0
    • 'ccx': Nope
  • 'x': Since cost[3] was previously entered a cost, we don't need to init. Expanding...
    • 'cx': Nope
  • Cost to cut entire string: cost[3] = 0
So there you go. With this method, you are assured that remaining substring (or 'previous state') to the left of the current palindrome is the minimum at that point because you already computed it earlier. You just need to +1 to the cost and see if you have a new minimum cost for the state you are currently in (the last character of the current palindrome).
int[] cost; public int minCut(String s) { if (s == null || s.length() < 2) return 0; int N = s.length(); cost = new int[N]; for (int i = 0; i < N; i++) cost[i] = Integer.MAX_VALUE; cut(s); return cost[N-1]; } private void cut (String s) { if (s.length() > 0) cost[0] = 0; if (s.length() > 1) cost[1] = s.charAt(1) == s.charAt(0) ? 0 : 1; int k = 0, l = 0, ni = 0; for (int i = 2; i < s.length(); i++) { if (cost[i] == Integer.MAX_VALUE) cost[i] = cost[i-1]+1; for (int j = 1; j <= 2; j++) { for (k = i-j, l = i; k >= 0 && l <= s.length()-1 && s.charAt(k) == s.charAt(l); k--, l++) { int c = k == 0 ? 0 : cost[k-1]+1; if (cost[l] > c) cost[l] = c; } } } }

For Palindrome related problems, - DP and isPalindrome[][].

https://discuss.leetcode.com/topic/6414/dp-solution-some-thoughts
  1. return the mininum cut of the partition s => optimization => DP
  2. try to divide & conqure =>
public int minCutRecur(String s){
int n = s.length;
    //base case
    if(s < 2 || isPalindr(s)) return 0;
    int min = n - 1;
    for(int i = 1; i <= n - 1; i++){
        if(isPalindr(s)){
            min = Math.min(min, 1 + minCutRecur(s.substring(i)));
        }
    }
    
    return min;
}
However, sub problem overlapped (are not independent with each other).
  1. Use DP to build the solution from bottom up.
    public int minCut(String s) {
    int n = s.length();
         boolean[][] isPalindr = new boolean[n + 1][n + 1]; //isPalindr[i][j] = true means s[i:j) is a valid palindrome
         int[] dp = new int[n + 1]; //dp[i] means the minCut for s[0:i) to be partitioned 
    
         for(int i = 0; i <= n; i++) dp[i] = i - 1;//initialize the value for each dp state.
         
         for(int i = 2; i <= n; i++){
             for(int j = i - 1; j >= 0; j--){
                 //if(isPalindr[j][i]){
                 if(s.charAt(i - 1) == s.charAt(j) && (i - 1 - j < 2 || isPalindr[j + 1][i - 1])){
                     isPalindr[j][i] = true;
                     dp[i] = Math.min(dp[i], dp[j] + 1);
                 }
             }
         }
         
         return dp[n];
    
    }
Several optimizations include:
  1. No need to check if a string is a palindrome or not inside the loop by adjusting the order of getting of solution of the sub problems.
  2. assign dp[0] to be -1 so that when s[0:i) is a palindrome by itself, dp[i] is 0. This is for the consistency of the code.
The time complexity and the space complexity are both O(n ^ 2).

http://www.jiuzhang.com/solutions/palindrome-partitioning-ii/
https://segmentfault.com/a/1190000007660424
用cuts[i]表示当前位置最少需要切几次使每个部分都是回文。如果s(j,i)这部分是回文,就有cuts[i] = cuts[j-1] + 1。
现在我们需要做的就是对于已经搜索并确定的回文部分,用一个二维数组来表示。matrix[j] [i]表示j到i这部分是回文。
如果s.charAt(i) == s.charAt(j) && isPalindrome[j+1] [i-1]是回文,则不需重复该部分的搜索。isPalindrome[j] [i]也是回文。
以"abcccba"为例:
i不断向后扫描, j从头开始知道i(包含i).
i=3即第二个c那里,j走到2, c[i] == c[j] == 'c' && i - j = 1 < 2, 填表,求最值。
i=4即第三个c那里,j走到2, c[i] == c[j] == 'c' && isPalindrome(2+1,4-1), 填表,求最值。
i=5即第二个b那里,j走到1, c[i] == c[j] == 'b' && isPalindrome(1+1,5-1)即“ccc“, 填表,求最值。
使用isPalindrome的好处就是可以O(1)的时间,也就是判断头尾就可以确定回文。不需要依次检查中间部分。


No comments:

Post a Comment

Labels

GeeksforGeeks (1107) LeetCode (993) Algorithm (795) Review (766) to-do (633) LeetCode - Review (514) Classic Algorithm (324) Dynamic Programming (293) Classic Interview (288) Google Interview (242) Tree (145) POJ (139) Difficult Algorithm (132) LeetCode - Phone (127) EPI (125) Different Solutions (120) Bit Algorithms (118) Lintcode (113) Cracking Coding Interview (110) Smart Algorithm (109) Math (107) HackerRank (89) Binary Tree (82) Binary Search (81) Graph Algorithm (74) Greedy Algorithm (72) DFS (67) LeetCode - Extended (62) Interview Corner (61) Stack (60) List (58) Advanced Data Structure (56) BFS (54) Codility (54) ComProGuide (52) Algorithm Interview (50) Geometry Algorithm (48) Binary Search Tree (46) USACO (46) Trie (45) Mathematical Algorithm (42) ACM-ICPC (41) Interval (41) Data Structure (40) Knapsack (40) Space Optimization (40) Jobdu (39) LeetCode Hard (39) Recursive Algorithm (39) Matrix (38) String Algorithm (38) Backtracking (36) Codeforces (36) Introduction to Algorithms (36) Must Known (36) Beauty of Programming (35) Sort (35) Union-Find (34) Array (33) prismoskills (33) Segment Tree (32) Sliding Window (32) Data Structure Design (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Company-Airbnb (29) Company-Zenefits (28) Microsoft 100 - July (28) Palindrome (28) to-do-must (28) Priority Queue (27) Random (27) Graph (26) Company - LinkedIn (25) GeeksQuiz (25) Logic Thinking (25) Pre-Sort (25) hihocoder (25) Queue (24) Company-Facebook (23) High Frequency (23) Post-Order Traverse (23) TopCoder (23) Algorithm Game (22) Bisection Method (22) Hash (22) Binary Indexed Trees (21) DFS + Review (21) Lintcode - Review (21) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Merge Sort (20) O(N) (20) Follow Up (19) Time Complexity (19) Two Pointers (19) UVA (19) Ordered Stack (18) Probabilities (18) Company-Uber (17) Game Theory (17) Topological Sort (17) Codercareer (16) Heap (16) Shortest Path (16) String Search (16) Tree Traversal (16) itint5 (16) Difficult (15) Iterator (15) BST (14) Number (14) Number Theory (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Euclidean GCD (13) KMP (13) Long Increasing Sequence(LIS) (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) LeetCode - Classic (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) Reverse Thinking (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Miscs (11) Princeton (11) Proof (11) Tree DP (11) X Sum (11) 挑战程序设计竞赛 (11) Bisection (10) Bucket Sort (10) Coin Change (10) Company - Microsoft (10) DFS+Cache (10) Facebook Hacker Cup (10) HackerRank Easy (10) O(1) Space (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) DP-Multiple Relation (9) DP-Space Optimization (9) Divide and Conquer (9) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Prefix Sum (9) Quick Sort (9) Simulation (9) Stack Overflow (9) Stock (9) System Design (9) TreeMap (9) Use XOR (9) Book Notes (8) Bottom-Up (8) Company-Amazon (8) DFS+BFS (8) LeetCode - DP (8) Left and Right Array (8) Linked List (8) Longest Common Subsequence(LCS) (8) Prime (8) Suffix Tree (8) Tech-Queries (8) Traversal Once (8) 穷竭搜索 (8) Algorithm Problem List (7) Expression (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Inversion (7) Kadane’s Algorithm (7) Level Order Traversal (7) Math-Divisible (7) Probability DP (7) Quick Select (7) Radix Sort (7) n00tc0d3r (7) 蓝桥杯 (7) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) DP-Print Solution (6) Dijkstra (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Manacher (6) Minimum Spanning Tree (6) Morris Traversal (6) Multiple Data Structures (6) One Pass (6) Programming Pearls (6) Pruning (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Stream (6) Suffix Array (6) Threaded (6) TreeSet (6) Xpost (6) reddit (6) AI (5) Algorithm - Brain Teaser (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) Cycle (5) DP-Include vs Exclude (5) Fast Slow Pointers (5) Find Rule (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) Matrix Chain Multiplication (5) Maze (5) Microsoft Interview (5) Pre-Sum (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sudoku (5) Sweep Line (5) Word Search (5) jiuzhang (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Abbreviation (4) Anagram (4) Anagrams (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Consistent Hash (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) LeetCode - Recursive (4) LeetCode - TODO (4) MST (4) MinMax (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Probability (4) Programcreek (4) Spell Checker (4) Stock Maximize (4) Subset Sum (4) Subsets (4) Symbol Table (4) Triangle (4) Water Jug (4) algnotes (4) fgdsb (4) to-do-2 (4) 最大化最小值 (4) A Star (3) Algorithm - How To (3) Algorithm Design (3) B Tree (3) Big Data Algorithm (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Finite Automata (3) Github (3) GoLang (3) Graph - Bipartite (3) Include vs Exclude (3) Joseph (3) Jump Game (3) K (3) Knapsack-多重背包 (3) LeetCode - Bit (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) O(N) Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Shuffle (3) Sieve of Eratosthenes (3) Stack - Smart (3) State Machine (3) Subtree (3) Transform Tree (3) Trie + DFS (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Ladder (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binary Search - Smart (2) Binomial Coefficient (2) Bit Counting (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Company-Snapchat (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) Edit Distance (2) Factor (2) Forward && Backward Scan (2) GoHired (2) Graham Scan (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) Math-Remainder Queue (2) Matrix Power (2) Median (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Parent-Only Tree (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Regular Expression (2) Return Multiple Values (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Tree Without Tree Predefined (2) Word Break (2) Word Graph (2) Word Trie (2) Yahoo Interview (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Augmented BST (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Sarch Tree (1) Binary String (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Cloest (1) Clone (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Cont Improvement (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Diagonal (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Knuth Shuffle (1) Kosaraju’s algorithm (1) Kruskal (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Machine Learning (1) Maintain State (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-End BFS (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Element (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parenthesis (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) PreProcess (1) Probabilistic Data Structure (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) Square (1) Streaming Algorithm (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Test Cases (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Virtual Matrix (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts