LeetCode 91 - Decode Ways


Related: LeetCode 639 - Decode Ways II
Count Possible Decodings of a given Digit Sequence
LeetCode - Decode Ways | Darren's Blog
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
Input: digits[] = "1234"
Output: 3
// The possible decodings are "ABCD", "LCD", "AWD"
We initialize the total count of decodings as 0. We recur for two subproblems.
1) If the last digit is non-zero, recur for remaining (n-1) digits and add the result to total count.
2) If the last two digits form a valid character (or smaller than 27), recur for remaining (n-2) digits and add the result to total count.
Transformation function as:
Count[i] = Count[i-1]  if S[i-1] is a valid char
       or   = Count[i-1]+ Count[i-2]  if S[i-1] and S[i-2] together is still a valid char.
X. DP

1.为什什么要⽤用DP？（因为是⼀一个⼀一个字符decode的，有递推的关系，⽽而
且明显有最优⼦子结构）
2. 可以⽤用递归吗？（递归可以求出解，但是是指数级复杂度的，然⽽而如果
⽤用记忆化搜索的话可以降到和DP⼀一样的复杂度）
3. 如果出现连续两个零会怎样？（答案肯定为零。然后加了了⼀行代码，遇
到连续两个零直接返回）
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/091_Decode_Ways.java
    public int numDecodings(String s) {
        int[] f = new int[s.length() + 1];
        f[0] = 1;
        int last = 0, last2 = 0;
        for (int i = 0; i < s.length(); i ++) {
            last  = s.charAt(i) - '0';
            last2 = last2 % 10 * 10 + last;
            if (last > 0) f[i + 1] = f[i];
            if (last2 > 9 && last2 < 27)
                f[i + 1] += f[i - 1];
        }
        return f[s.length()];
    }

https://leetcode.com/discuss/83547/java-clean-dp-solution-with-explanation
https://discuss.leetcode.com/topic/20456/dp-with-easy-understand-java-solution/2
https://leetcode.com/discuss/8527/dp-solution-java-for-reference
I used a dp array of size n + 1 to save subproblem solutions. dp[0] means an empty string will have one way to decode, dp[1] means the way to decode a string of size 1. I then check one digit and two digit combination and save the results along the way. In the end, dp[n] will be the end result.
public int numDecodings(String s) { if(s == null || s.length() == 0) { return 0; } int n = s.length(); int[] dp = new int[n+1]; dp[0] = 1; dp[1] = s.charAt(0) != '0' ? 1 : 0; for(int i = 2; i <= n; i++) { int first = Integer.valueOf(s.substring(i-1, i)); int second = Integer.valueOf(s.substring(i-2, i)); if(first >= 1 && first <= 9) { dp[i] += dp[i-1]; } if(second >= 10 && second <= 26) { dp[i] += dp[i-2]; } } return dp[n]; }
https://discuss.leetcode.com/topic/2562/dp-solution-java-for-reference
http://shanjiaxin.blogspot.com/2014/04/decode-ways-leetcode.html
public int numDecodings(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int n = s.length();
        // table[i]: the number of decodings for s[i...]
        int[] table = new int[n+1];
        // table[n]: upon reaching the end, earlier digit(s) is a way of decoding itself
        // It is used to handle the cases such as s="15"
        table[n] = 1;
        // Consider the last digit individually
        char last = s.charAt(n-1);
        if (last >= '1' && last <= '9')
            table[n-1] = 1;
        // Calculate table[i] according to s[i], table[i+1], and table[i+2]
        for (int i = n-2; i >= 0; i--) {
            char c = s.charAt(i);
            if (c < '1' || c > '9')     // s[i...] starts with invalid digit
                table[i] = 0;
            else if (c > '2' || c == '2' && s.charAt(i+1) > '6')    // s[i,i+1] must be decoded together
                table[i] = table[i+1];
            else    // Decoded as s[i], s[i+1...], or s[i,i+1], s[i+2...]
                table[i] = table[i+1] + table[i+2];
        }
        // Return the number of decodings for s
        return table[0];
    }

 http://www.jiuzhang.com/solutions/decode-ways/
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] nums = new int[s.length() + 1];
        nums[0] = 1;
        nums[1] = s.charAt(0) != '0' ? 1 : 0;
        for (int i = 2; i <= s.length(); i++) {
            if (s.charAt(i - 1) != '0') {
                nums[i] = nums[i - 1];
            }
            
            int twoDigits = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
            if (twoDigits >= 10 && twoDigits <= 26) {
                nums[i] += nums[i - 2];
            }
        }
        return nums[s.length()];
    }
http://www.jyuan92.com/blog/leetcode-decode-ways/
public int numDecodings(String s) {
    if (null == s || s.length() == 0 || s.charAt(0) == '0') {
        return 0;
    }
    int[] dp = new int[s.length() + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= s.length(); i++) {
        if (isValid(s.substring(i - 1, i))) {
            dp[i] += dp[i - 1];
        }
        if (isValid(s.substring(i - 2, i))) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[s.length()];
}
private boolean isValid(String s) {
    if (s.charAt(0) == '0') {
        return false;
    }
    int num = Integer.parseInt(s);
    return num > 0 && num < 27;
}
http://rleetcode.blogspot.com/2014/01/decode-ways-java.html
public int numDecodings(String s) {
    if (s==null||s.length()==0){
        return 0;
    }
 
    // declare ways array with two extra space, because ways[i] also affect by ways[i+2]
    int[] ways=new int[s.length()+2];
 
 
    Arrays.fill(ways, 1);
    int i=s.length()-1;
 
    ways[i]=s.charAt(i)=='0'?0:1;
 
    for (i=i-1; i>=0; i--){
        if (s.charAt(i)=='0'){
            // if current digit is '0', so no mater what right is, current ways should be 0;
            ways[i]=0;
        }
        else{
           // if current digit is not '0', current ways should be ways[i+1]
           // because, for example s="12", i=0, ways[1]=1, then because current digit is not zero, so for
           // each situation of when i=1, the current i=0 should  be a valid way,
            ways[i]=ways[i+1];
     
     
        // check is current digit with right 1 digit can be a valid situation,so in this situation only s.charAt(i)=='1'||
        // s.charAt(i)=='2' and s.charAt(i+1)<='6' can be valid situation, the ways[i] should + ways[i+2];
     
            if (i+2<ways.length && s.charAt(i)=='1'||s.charAt(i)=='2' &&s.charAt(i+1)<='6'){
                ways[i]+=ways[i+2];
           }
        }
    }
 
    return ways[0];
}

http://bangbingsyb.blogspot.com/2014/11/leetcode-decode-ways.html
    int numDecodings(string s) {
        if(s.empty() || s[0]<'1' || s[0]>'9') return 0;
        vector<int> dp(s.size()+1,0);
        dp[0] = dp[1] = 1;
        
        for(int i=1; i<s.size(); i++) {
            if(!isdigit(s[i])) return 0;
            int v = (s[i-1]-'0')*10 + (s[i]-'0');
            if(v<=26 && v>9) dp[i+1] += dp[i-1];
            if(s[i]!='0') dp[i+1] += dp[i];
            if(dp[i+1]==0) return 0;
        }
        return dp[s.size()];
    }
Also check Count Possible Decodings of a given Digit Sequence
Time Complexity of the above solution is O(n) and it requires O(n) auxiliary space. We can reduce auxiliary space to O(1) by using space optimized version discussed in the Fibonacci Number Post.

int countDecodingDP(char *digits, int n)
{
    int count[n+1]; // A table to store results of subproblems
    count[0] = 1;
    count[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        count[i] = 0;
        // If the last digit is not 0, then last digit must add to
        // the number of words
        if (digits[i-1] > '0')
            count[i] = count[i-1];
        // If second last digit is smaller than 2 and last digit is
        // smaller than 7, then last two digits form a valid character
        if (digits[i-2] < '2' || (digits[i-2] == '2' && digits[i-1] < '7') )
            count[i] += count[i-2];
    }
    return count[n];
}
http://n00tc0d3r.blogspot.com/2013/02/the-number-of-ways-to-decode-message.html
private boolean isTwoDigitCode(char a, char b) {  
   return (a=='1' || (a=='2' && b<='6'));  
 }  
   
 public int numDecodings(String s) {  
   int len = s.length();  
     
   int[] count = new int[len+1];  
   count[0] = (len <= 0) ? 0 : 1;
   for (int i=1; i<=len; ++i) {  
     char c = s.charAt(i-1);
     if ( c != '0' )  count[i] = count[i-1];  
     if ( i-1 > 0 && isTwoDigitCode(s.charAt(i-2), c) ) {  
       count[i] += count[i-2];  
     }  
     if ( count[i] == 0 ) return 0;  // invalid
   }  
   return count[len];  
 }

https://discuss.leetcode.com/topic/45327/java-2ms-dp-solution-with-detailed-explanation-and-inline-comments

X. DP -O(1) space:
https://discuss.leetcode.com/topic/39698/share-my-2ms-java-solution-with-o-1-spqce
public int numDecodings(String s) {
    if(s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
 int curWays = 1;
 int preWays = 1;
 int length = s.length();
 for(int i = 1; i < length; i++){
  int newCurWays = curWays;
  if(s.charAt(i) == '0'){
   if(s.charAt(i - 1) != '1' && s.charAt(i - 1) != '2') return 0;
   else newCurWays = preWays; 
  }else if(s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) < '7')){
   newCurWays += preWays;
  }
  preWays = curWays;
  curWays = newCurWays;
 }
 return curWays;
}
https://discuss.leetcode.com/topic/7025/a-concise-dp-solution
int numDecodings(string s) {
    if (!s.size() || s.front() == '0') return 0;
    // r2: decode ways of s[i-2] , r1: decode ways of s[i-1] 
    int r1 = 1, r2 = 1;
    
    for (int i = 1; i < s.size(); i++) {
        // zero voids ways of the last because zero cannot be used separately
        if (s[i] == '0') r1 = 0;

        // possible two-digit letter, so new r1 is sum of both while new r2 is the old r1
        if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6') {
            r1 = r2 + r1;
            r2 = r1 - r2;
        }

        // one-digit letter, no new way added
        else {
            r2 = r1;
        }
    }

    return r1;
}
we only need previous two counts, count[i-1] and count[i-2]. So, we can use two integers instead of an array! This can reduce the space usage to O(1).http://www.cnblogs.com/EdwardLiu/p/4020438.html

 2     public int numDecodings(String s) {
 3         if (s==null || s.length()==0 || s.charAt(0)=='0') {
 4             return 0;
 5         }
 6         int num1 = 1;
 7         int num2 = 1;
 8         int num3 = 1;
 9         for (int i=1; i<s.length(); i++) {
10             if (s.charAt(i) == '0') {
11                 if (s.charAt(i-1) == '1' || s.charAt(i-1) == '2') {
12                     num3 = num1;
13                 }
14                 else return 0;
15             }
16             else {
17                 if (s.charAt(i-1) == '0' || s.charAt(i-1) >= '3') {
18                     num3 = num2;
19                 }
20                 else if (s.charAt(i-1)=='2' && (s.charAt(i) =='7'||s.charAt(i)=='8'||s.charAt(i)=='9')) {
21                     num3 = num2;
22                 }
23                 else num3 = num2 + num1;
24             }
25             num1 = num2;
26             num2 = num3;
27         }
28         return num2;
29     }
Also check http://gongxuns.blogspot.com/2012/12/leetcodedecode-ways.html
https://github.com/tingyu/Leetcode/blob/master/Decode%20Ways/DecodeWays.java
 public int numDecodings(String s) {  
   int len = s.length();  
     
   int w1 = (len <= 0) ? 0 : 1, w2 = w1;  
   for (int i=1; i<=len; ++i) {  
     char c = s.charAt(i-1);
     int temp = w2; // w1 = count[i-2], temp = w2 = count[i-1]

     // update w2 to be count[i]
     if ( c == '0' )  w2 = 0;  
     if ( i-1 > 0 && isTwoDigitCode(s.charAt(i-2), c) ) {  
       w2 += w1;  
     }  
     if ( w2 == 0 ) return 0;  // invalid

     // set w1 = temp = count[i-1], i.e. A[(i+1)-2]
     w1 = temp;
   }  
   return w2;  
 }

X. Memoization
http://siyang2leetcode.blogspot.com/2015/03/decode-ways.html
 public int numDecodings(String s) {  
     if(s == null || s.length() == 0) return 0;  
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
     map. put(s.length(), 1);  
     return dfs(s, 0, map);  
   }  
   private int dfs(String s, int index, Map<Integer, Integer> map){  
     // check path memory  
     if(map.containsKey(index)) return map.get(index);  
     // recursion  
     int count = 0;  
     if(index+1 < s.length() &&(s.charAt(index) == '1' || s.charAt(index) == '2' && s.charAt(index+1) <= '6'))  
       count += dfs(s, index+2, map);  
     if(s.charAt(index) != 0)  
       count += dfs(s, index+1, map);  
     map.put(index, count);  
     return count;  
   }
https://leetcode.com/discuss/23872/sharing-my-java-memoized-solution
You write symbols.contains(str.substring(start, start + 1)) andsymbols.contains(str.substring(start, start + 2)) twice. But I love your approach. I think I can call it Path-Memorizing DFS. BTW, I tried simple DFS and get TLE. I think after path-memorizing, the time complexity is O(n). Great!
public int numDecodings(String s) { if (s == null || s.length() == 0) return 0; Set<String> symbols = new HashSet<String>(); for (int i=1; i<=26; i++){ symbols.add(String.valueOf(i)); } Map<Integer, Integer> map = new HashMap<Integer, Integer>(); return numDec(s, 0, map, symbols); } private int numDec(String str, int start, Map<Integer, Integer> map, Set<String> symbols) { Integer count = map.get(start); if (count != null){ return count; } if (start == str.length()){ return 1; } int numWays = 0; if ((start + 1 <= str. length()) && symbols.contains(str.substring(start, start + 1)) ) numWays += numDec(str, start + 1, map, symbols); if ((start + 2 <= str. length()) && symbols.contains(str.substring(start, start + 2)) ) numWays += numDec(str, start + 2, map, symbols); map.put(start, numWays); return numWays; }
X. Brute force(DFS), time complexity = O(2^n)
https://longwayjade.wordpress.com/2015/04/26/leetcode-recursion-dp-decode-ways/
    public int numDecodings(String s) {
        int len = s.length();
        if (len == 0) return 0;
        if (len == 1 ){
            if (isValid(s.substring(0,1))) return 1;
            else return 0;
        }
        int res = 0;
        // at least have two elements here.
        if (isValid(s.substring(len-1))) res += numDecodings(s.substring(0,len-1));
        if (isValid(s.substring(len-2))) res += numDecodings(s.substring(0,len-2));
        return res;
    }
     
    public boolean isValid (String s){
        if (s.length() == 0 ) return false;
        int i = Integer.parseInt(s);
        if ( i >= 1 && i <= 26 ) return true;
        else return false;
    }

http://siyang2leetcode.blogspot.com/2015/03/decode-ways.html
   public int numDecodings(String s) {  
     return dfs(s, 0);  
   }  
   private int dfs(String s, int index){  
     // base case  
     if(index >= s.length()) return 1;  
     // recursion  
     int count = 0;  
     if(index+1 < s.length() &&(s.charAt(index) == '1' || s.charAt(index) == '2' && s.charAt(index+1) <= '6'))  
       count += dfs(s, index+2);  
     if(s.charAt(index) != '0')  
       count += dfs(s, index+1);  
     return count;  
   }
http://www.geeksforgeeks.org/count-possible-decodings-given-digit-sequence/
1) If the last digit is non-zero, recur for remaining (n-1) digits and add the result to total count.
2) If the last two digits form a valid character (or smaller than 27), recur for remaining (n-2) digits and add the result to total count.
int countDecoding(char *digits, int n)
{
    // base cases
    if (n == 0 || n == 1)
        return 1;
    int count = 0;  // Initialize count
    // If the last digit is not 0, then last digit must add to
    // the number of words
    if (digits[n-1] > '0')
        count =  countDecoding(digits, n-1);
    // If the last two digits form a number smaller than or equal to 26,
    // then consider last two digits and recur
    if (digits[n-2] < '2' || (digits[n-2] == '2' && digits[n-1] < '7') )
        count +=  countDecoding(digits, n-2);
    return count;
}
http://zhaonanleetcode.blogspot.com/2014/06/leetcode-decode-ways.html
public class Solution {
    int counter;
    public int numDecodings(String s) {
        // Input validation.
        if (s == null || s.length() == 0) return 0;
        if (s.length() == 1) return 1;

        counter = 0;
        int len = s.length();
        int start = 0;

        helper(s, len, start);

        return counter;
    }

    public void helper(String s, int len, int start) {
        // Base case.
        if (start >= len) {
            counter ++;
            return;
        }

        // Try one letter.
        helper(s, len, start + 1);

        // Try two letters.
        if (start + 1 < len) {
            char curr = s.charAt(start);
            char next = s.charAt(start + 1);
            int number = ((int)curr - (int)'0')* 10 + ((int)next - (int)'0');

            if (number <= 26) {
                helper(s, len, start + 2);
            }
        }
    }
}
Read full article from LeetCode - Decode Ways | Darren's Blog
at
Labels: , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts