Sunday, December 11, 2016

LeetCode 471 - Encode String with Shortest Length


Related: LeetCode 394 - Decode String
http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/
Given a non-empty string, encode the string such that its encoded length is the shortest.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.
Note:
  1. k will be a positive integer and encoded string will not be empty or have extra space.
  2. You may assume that the input string contains only lowercase English letters. The string's length is at most 160.
  3. If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them is fine.
Example 1:
Input: "aaa"
Output: "aaa"
Explanation: There is no way to encode it such that it is shorter than the input string, so we do not encode it.
Example 2:
Input: "aaaaa"
Output: "5[a]"
Explanation: "5[a]" is shorter than "aaaaa" by 1 character.
Example 3:
Input: "aaaaaaaaaa"
Output: "10[a]"
Explanation: "a9[a]" or "9[a]a" are also valid solutions, both of them have the same length = 5, which is the same as "10[a]".
Example 4:
Input: "aabcaabcd"
Output: "2[aabc]d"
Explanation: "aabc" occurs twice, so one answer can be "2[aabc]d".
Example 5:
Input: "abbbabbbcabbbabbbc"
Output: "2[2[abbb]c]"
Explanation: "abbbabbbc" occurs twice, but "abbbabbbc" can also be encoded to "2[abbb]c", so one answer can be "2[2[abbb]c]".
https://chenboxie.wordpress.com/2018/07/08/leetcode-471-encode-string-with-shortest-length/
区间DP的问题,我们用dp[i][j]表示子串s[i:j]的最小压缩串,我们有如下递推方程:
  • dp[i][j] = min(dp[i][k] + dp[k + 1][j]), where 1 <= k < j, ‘+’ means concatenate here
  • dp[i][j] = min(dp[i][j], compress(s[i:j])), compress is a function to find if we can shorten input string by find a repeating pattern in itself
这里两个递推公式,第一个递推适用于 abcabcd这种string,在k = 5的时候, dp(abcabcd) = dp(abcabc) + dp(d) = 2[abc] + d = 2[abc]d
2. 但仅仅使用第一个递推是不够的,例如这个例子,abcabcabc, 用第一个递推公式可以得到, dp(abcabcabc) = dp(abcabc) + dp(abc) = 2[abc] + abc = 2[abc]abc,永远无法得到3[abc]
所以由此我们需要第二个递推:
这里compress的功能是,找到string自身的重复串来压缩string。比如对于abcabcabc,我们只进行区间dp是没有办法找到3[abc]的,所以我们必须对自身进行compress。
这里就引出很重要的一个技巧:
我们在字符串t后面再加上一个t,然后在这里面寻找子字符串t的第二个起始位置,如果第二个起始位置小于t的长度的话,说明t包含重复字符串,举个例子吧,比如 t = “abab”, 那么t+t = “abababab”,我们在里面找第二个t出现的位置为2,小于t的长度4,说明t中有重复出现,重复的个数为t.size()/pos = 2个
3. 假设自身的字符串为sub, 在对自身进行压缩的过程中,如果自身是符合压缩条件的,压缩必须写成:
sub = sub.length() / index + “[” + dp[i][i + index – 1] + “]”;
举个例子,比如
sub = “abcdbcd abcdbcd”,不能写成2[abcdbcd], 而是写成2[a2[bcd]]
总结:
1. 区间DP的辨别和运用,dp[i][j] = max/min(dp[i][k] + dp[k + 1][j])
2. 像s=abcabc这样的字符串,在O(n)时间内进行压缩的方法,就是在s + s中寻找s的第二个起始位置,如果第二个起始位置小于s的长度的话,说明s包含重复字符串。
这道题还是应该用动态规划来做。我们建立一个二维的DP数组,其中dp[i][j]表示s在[i, j]范围内的字符串的缩写形式(如果缩写形式长度大于子字符串,那么还是保留子字符串),那么如果s字符串的长度是n,最终我们需要的结果就保存在dp[0][n-1]中,然后我们需要遍历s的所有子字符串,对于任意一段子字符串[i, j],我们我们以中间任意位置k来拆分成两段,比较dp[i][k]加上dp[k+1][j]的总长度和dp[i][j]的长度,将长度较小的字符串赋给dp[i][j],然后我们要做的就是在s中取出[i, j]范围内的子字符串t进行合并。合并的方法是我们在取出的字符串t后面再加上一个t,然后在这里面寻找子字符串t的第二个起始位置,如果第二个起始位置小于t的长度的话,说明t包含重复字符串,举个例子吧,比如 t = "abab", 那么t+t = "abababab",我们在里面找第二个t出现的位置为2,小于t的长度4,说明t中有重复出现,重复的个数为t.size()/pos = 2个,那么我们就要把重复的地方放入中括号中,注意中括号里不能直接放这个子字符串,而是应该从dp中取出对应位置的字符串,因为重复的部分有可能已经写成缩写形式了,比如题目中的例子5。如果t = "abc",那么t+t = "abcabc",我们在里面找第二个t出现的位置为3,等于t的长度3,说明t中没有重复出现,那么replace就还是t。然后我们比较我们得到的replace和dp[i][j]中的字符串长度,把长度较小的赋给dp[i][j]即可,时间复杂度为O(n3),空间复杂度为O(n2)。

这里compress的功能是,找到string自身的重复串来压缩string。比如对于abcabcabc,我们只进行区间dp是没有办法找到3[abc]的,所以我们必须对自身进行compress。对自身进行压缩的就是寻找自身最小覆盖子串的过程。有多个覆盖子串我们肯定是取最小的,对于d[str]的形式,如果我们double str的长度最多也就使得d减少一位,所以str越短越好。
时间复杂度O(n^3),寻找自身最小覆盖子串需要线性时间,代码如下:

https://discuss.leetcode.com/topic/71963/accepted-solution-in-java
We will form 2-D array of Strings.
dp[i][j] = string from index i to index j in encoded form.
We can write the following formula as:-
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) or if we can find some pattern in string from i to j which will result in more less length.
Time Complexity = O(n^3)
Time Complexity is O(N^4), replaceAll() is O(N)
    String[][] dp = new String[s.length()][s.length()];
    
    for(int l=0;l<s.length();l++) {
        for(int i=0;i<s.length()-l;i++) {
            int j = i+l;
            String substr = s.substring(i, j+1);
            // Checking if string length < 5. In that case, we know that encoding will not help.
            if(j - i < 4) {
                dp[i][j] = substr;
            } else {
                dp[i][j] = substr;
                // Loop for trying all results that we get after dividing the strings into 2 and combine the   results of 2 substrings
                for(int k = i; k<j;k++) {
                    if((dp[i][k] + dp[k+1][j]).length() < dp[i][j].length()){
                        dp[i][j] = dp[i][k] + dp[k+1][j];
                    }
                }
                
                // Loop for checking if string can itself found some pattern in it which could be repeated.
                for(int k=0;k<substr.length();k++) {
                    String repeatStr = substr.substring(0, k+1);
                    if(repeatStr != null 
                       && substr.length()%repeatStr.length() == 0 
                       && substr.replaceAll(repeatStr, "").length() == 0) {
                          String ss = substr.length()/repeatStr.length() + "[" + dp[i][i+k] + "]";
                          if(ss.length() < dp[i][j].length()) {
                            dp[i][j] = ss;
                          }
                     }
                }
            }
        }
    }
    
    return dp[0][s.length()-1];
}

X.
http://www.cnblogs.com/grandyang/p/6194403.html
我们建立一个二维的DP数组,其中dp[i][j]表示s在[i, j]范围内的字符串的缩写形式(如果缩写形式长度大于子字符串,那么还是保留子字符串),那么如果s字符串的长度是n,最终我们需要的结果就保存在dp[0][n-1]中,然后我们需要遍历s的所有子字符串,对于任意一段子字符串[i, j],我们我们以中间任意位置k来拆分成两段,比较dp[i][k]加上dp[k+1][j]的总长度和dp[i][j]的长度,将长度较小的字符串赋给dp[i][j],

然后我们要做的就是在s中取出[i, j]范围内的子字符串t进行合并。合并的方法是我们在取出的字符串t后面再加上一个t,然后在这里面寻找子字符串t的第二个起始位置,如果第二个起始位置小于t的长度的话,说明t包含重复字符串,举个例子吧,比如 t = "abab", 那么t+t = "abababab",我们在里面找第二个t出现的位置为2,小于t的长度4,说明t中有重复出现,重复的个数为t.size()/pos = 2个,那么我们就要把重复的地方放入中括号中,注意中括号里不能直接放这个子字符串,而是应该从dp中取出对应位置的字符串,因为重复的部分有可能已经写成缩写形式了,比如题目中的例子5。如果t = "abc",那么t+t = "abcabc",我们在里面找第二个t出现的位置为3,等于t的长度3,说明t中没有重复出现,那么replace就还是t。然后我们比较我们得到的replace和dp[i][j]中的字符串长度,把长度较小的赋给dp[i][j]即可,时间复杂度为O(n3),空间复杂度为O(n2),

    string encode(string s) {
        int n = s.size();
        vector<vector<string>> dp(n, vector<string>(n, ""));
        for (int step = 1; step <= n; ++step) {
            for (int i = 0; i + step - 1 < n; ++i) {
                int j = i + step - 1;
                dp[i][j] = s.substr(i, step);
                for (int k = i; k < j; ++k) {
                    string left = dp[i][k], right = dp[k + 1][j];
                    if (left.size() + right.size() < dp[i][j].size()) {
                        dp[i][j] = left + right;
                    }
                }
                string t = s.substr(i, j - i + 1), replace = "";
                auto pos = (t + t).find(t, 1);
                if (pos >= t.size()) replace = t;
                else replace = to_string(t.size() / pos) + '[' + dp[i][i + pos - 1] + ']';
                if (replace.size() < dp[i][j].size()) dp[i][j] = replace;
            }
        }
        return dp[0][n - 1];
    }

我们可以优化上面的方法。如果t是重复的,是不是就不需要再看left.size() + right.size() < dp[i][j].size()了。例如t是abcabcabcabcabc, 最终肯定是5[abc],不需要再看3[abc]+abcabc或者abcabc+3[abc]。对于一个本身就重复的字符串,最小的长度肯定是n[REPEATED],不会是某个left+right。所以应该把k的那个循环放在t和replace那部分代码的后面。这样的确提高了一些运算效率的

    string encode(string s) {
        int n = s.size();
        vector<vector<string>> dp(n, vector<string>(n, ""));
        for (int step = 1; step <= n; ++step) {
            for (int i = 0; i + step - 1 < n; ++i) {
                int j = i + step - 1;
                dp[i][j] = s.substr(i, step);
                string t = s.substr(i, j - i + 1), replace = "";
                auto pos = (t + t).find(t, 1);
                if (pos < t.size()) {
                    replace = to_string(t.size() / pos) + "[" + dp[i][i + pos - 1] + "]";
                    if (replace.size() < dp[i][j].size()) dp[i][j] = replace;
                    continue;
                }
                for (int k = i; k < j; ++k) {
                    string left = dp[i][k], right = dp[k + 1][j];
                    if (left.size() + right.size() < dp[i][j].size()) {
                        dp[i][j] = left + right;
                    }
                }
            }
        }
        return dp[0][n - 1];
    }

https://segmentfault.com/a/1190000008341304
dpi表示s[i, j]最短的压缩结果,subproblem里面枚举切分点k,分别得到dpi和dpk+1求和,找到长度最短的。
这道题关键是找sub = abcabc这种可压缩的情况,其中sub = s[i,j]。方法比较巧妙,用sub+sub = abcabcabcabc,找第二个s在s+s里出现的位置,如果不是len(sub),则说明sub有重复,那么就要压缩这个sub,重复次数是len(sub) / indexOf(sub, 1),重复的string用的是之前压缩过的dpi,index = indexOf(sub, 1)。
    public String encode(String s) {
        int n = s.length();
        String[][] dp = new String[n][n];
        for(int i = 0; i < n; i++) dp[i][i] = "" + s.charAt(i);
        // j - i
        for(int len = 1; len < n; len++) {
            for(int i = 0; i + len < n; i++) {
                int j = i + len;
                // enumerate seperate k
                for(int k = i; k < j; k++) {
                    int left = dp[i][k].length();
                    int right = dp[k+1][j].length();
                    // update shortest encoded string within (i, j)
                    if(dp[i][j] == null || left + right < dp[i][j].length()) {
                        dp[i][j] = dp[i][k] + dp[k+1][j];
                    }
                }
                // update string within (i, j), encode abcabc
                String sub = s.substring(i, j + 1);
                int index = (sub + sub).indexOf(sub, 1);
                if(index < sub.length()) {
                    sub = (sub.length() / index) + "[" + dp[i][i+index-1] + "]";
                }
                if(dp[i][j] == null || dp[i][j].length() > sub.length()) {
                    dp[i][j] = sub;
                }
            }
        }
        
        return dp[0][n-1];
    }
http://www.cnblogs.com/EdwardLiu/p/6213476.html
Initially I think of 1D DP, dp[i] stands for the shortest string of first i characters, then:
dp[i] = minLen{dp[k] + encode(substring(k+1, i))}
then I realize that the second part encode(substring(k+1, i)) is actually the same with our dp problem. So it turns out the transfer function is
dp[i] = minLen{dp[k] + dp(substring(k+1, i))}
then 1D is not enough, I introduce the second dimension, which indicates the end. dp[i][j] is the shortest encoded string from i to j
But the hardest part of this problem is how to generate dp[i][j] from dp[i][k] and dp[k+1][j]
I‘ve thought about the cases like: 
dp[i][k] = 3[abc]   dp[k+1][j] = 2[abc],   then dp[i][j] = 5[abc]
dp[i][k] = 3[abc]   dp[k+1][j] = xyz,   then dp[i][j] = 3[abc]xyz
dp[i][k] = aabc   dp[k+1][j] = aabc,   then dp[i][j] = 2[aabc]
No idea what to implement this conveniently, so refer to idea  
The idea is to firstly concantenate dp[i][k] and dp[k+1][j] directly to construct dp[i][j], and then check if there exist possible repeat patterns in the original substring s.substring(i, j+1) that could further shorten dp[i][j]


replaceAll function is really clever
https://hbisheng.gitbooks.io/leetcode-google/content/471-encode-string-with-shortest-length.html
记忆化搜索
利用字典dp记录字符串的最优编码串

枚举分隔点p, 将字符串拆解为left, right左右两部分

尝试将left调用solve函数进行编码压缩,并对right递归调用encode函数进行搜索

将left和right组合的最短字符串返回,并更新dp
def __init__(self): self.dp = dict() def encode(self, s): """ :type s: str :rtype: str """ size = len(s) if size <= 1: return s if s in self.dp: return self.dp[s] ans = s for p in range(1, size + 1): left, right = s[:p], s[p:] t = self.solve(left) + self.encode(right) if len(t) < len(ans): ans = t self.dp[s] = ans return ans def solve(self, s): ans = s size = len(s) for x in range(1, size / 2 + 1): if size % x or s[:x] * (size / x) != s: continue y = str(size / x) + '[' + self.encode(s[:x]) + ']' if len(y) < len(ans): ans = y return ans


https://yijiajin.github.io/leetcode/2017/01/02/LC471.-Encode-String-with-Shortest-Length/
利用KMP算法来寻找和判断是否存在重复的子串是比较快的。顺便这是LC459题。
public String encode(String s) { // dp solution, for each substring of s, check whether it can be encode // dp[i][j] means substing of [i, j] after encode if(s == null || s.length() <= 4) return s; int len = s.length(); String[][] dp = new String[len][len]; for(int sublen = 0; sublen < len; sublen++){ for(int begin = 0; begin < len - sublen; begin++){ int end = begin + sublen; String sub = s.substring(begin, end + 1); dp[begin][end] = sub; if(sublen < 4) continue; // sub.length = sublen + 1 // get shortest substring combination for(int i = begin; i < end; i++){ if(dp[begin][i].length() + dp[i+1][end].length() < dp[begin][end].length()) dp[begin][end] = dp[begin][i] + dp[i+1][end]; } // if repeat, using kmp to encode then compare with shortest combination String pattern = kmp(sub); //System.out.println(pattern); // no repeat, keep origional -> shorest combination  if(pattern.length() == sub.length()) continue; // find repeat, repeat should also be encoded String encode = sub.length()/pattern.length() + "[" + dp[begin][begin+pattern.length()-1] + "]"; if(encode.length() < dp[begin][end].length()) dp[begin][end] = encode; } // for begin  } // for sublen return dp[0][len - 1]; } // code // kmp method to find repeat pattern in one String private String kmp(String str){ int len = str.length(); int[] next = new int[len]; char[] arr = str.toCharArray(); Arrays.fill(next, -1); int i = 0, j = 1; for(; j < len; j++){ i = next[j - 1]; while(arr[i + 1] != arr[j] && i >= 0) i = next[i]; if(arr[i + 1] == arr[j]) next[j] = i + 1; else next[j] = -1; } //System.out.println(Arrays.toString(next)); // if repeat, it must before the 0 int patternLen = len - next[len - 1] - 1; if(patternLen == 0) return str; if(patternLen != len && len % patternLen == 0) { return str.substring(0, patternLen); } else { return str; } } // kmp


No comments:

Post a Comment

Labels

LeetCode (1307) GeeksforGeeks (1119) LeetCode - Review (889) Review (880) Algorithm (674) to-do (609) Classic Algorithm (272) Google Interview (239) Classic Interview (223) Dynamic Programming (221) DP (167) Bit Algorithms (143) POJ (141) Math (135) Tree (133) LeetCode - Phone (128) EPI (122) Cracking Coding Interview (119) Difficult Algorithm (116) Lintcode (114) Different Solutions (110) DFS (105) Smart Algorithm (104) Binary Search (93) HackerRank (89) Binary Tree (87) BFS (79) Hard (75) Graph Algorithm (72) Stack (72) Two Pointers (72) Greedy Algorithm (69) BST (67) Interview Corner (61) LeetCode - Extended (61) Time Complexity (59) Geometry Algorithm (58) Interval (57) Advanced Data Structure (56) List (56) Trie (56) Codility (53) Union-Find (53) ComProGuide (50) LeetCode Hard (49) Priority Queue (49) Segment Tree (47) Bisection (46) Matrix (46) USACO (46) Sliding Window (45) Algorithm Interview (42) Mathematical Algorithm (41) Space Optimization (41) ACM-ICPC (40) Backtracking (40) Graph (39) Jobdu (39) Codeforces (38) Data Structure (38) Knapsack (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Data Structure Design (37) Tree - Post-Order (37) Introduction to Algorithms (36) Sort (36) Beauty of Programming (35) Must Known (34) Random (34) Binary Search Tree (33) Greedy (33) Pre-Sort (33) prismoskills (33) LeetCode - DP (32) Permutation (32) Array (31) Palindrome (31) Google Code Jam (30) HDU (30) Array O(N) (29) Company-Airbnb (29) Logic Thinking (29) Puzzles (29) Company-Zenefits (28) Monotonic Stack (28) Follow Up (27) Microsoft 100 - July (27) Queue (27) to-do-must (27) Binary Indexed Trees (26) Company-Facebook (25) GeeksQuiz (25) hihocoder (25) Company - LinkedIn (24) Hash (24) Reverse Thinking (24) High Frequency (23) TreeMap (23) Game Theory (22) Merge Sort (22) Proof (22) Summary (22) 1point3acres (21) Lintcode - Review (21) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Topological Sort (20) Algorithm Game (19) Brain Teaser (19) DP - Tree (19) Divide and Conquer (19) O(N) (19) UVA (19) Left and Right Array (18) Sweep Line (18) Tree - Modification (18) DP - Bit Masking (17) KMP (17) LeetCode - Thinking (17) Probabilities (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Shortest Path (16) itint5 (16) Euclidean GCD (15) Heap (15) Number Theory (15) Rolling Hash (15) DFS+Cache (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Dijkstra (14) Fast Power Algorithm (14) Long Increasing Sequence(LIS) (14) Number (14) Tree Traversal (14) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Company - Google (13) Computational Geometry (13) DP - Digit (13) LeetCode - DFS (13) Majority (13) O(1) Space (13) Reservoir Sampling (13) TreeSet (13) mitbbs (13) Algorithm - How To (12) Bucket Sort (12) Combination (12) DP - Multiple Relation (12) LCA (12) LeetCode - Classic (12) Math-Divisible (12) Prime (12) Pruning (12) Reconstruct Tree (12) Simulation (12) X Sum (12) AOJ (11) Bit Mask (11) Brute Force (11) Company - Microsoft (11) Company-Snapchat (11) DP - Interval (11) DP - Relation Optimization (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) Level Order Traversal (11) MinMax (11) Miscs (11) Prefix Sum (11) Princeton (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) HackerRank Easy (10) Interval Tree (10) Matrix - Traverse (10) Monotone Queue (10) Quick Sort (10) SPOJ (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Median (9) Quick Select (9) Stack Overflow (9) System Design (9) Thinking (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Fast Slow Pointers (8) LeetCode - TODO (8) Linked List (8) Longest Common Subsequence(LCS) (8) O(32N) (8) One Pass (8) Starting Point (8) Traversal Once (8) Tree - Conversion (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) DP - Cases (7) Expression (7) Facebook Interview (7) Fibonacci Numbers (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) O(XN) (7) Radix Sort (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Classic Data Structure Impl (6) Cycle (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) Flood fill (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) LeetCode - Hard (6) Local MinMax (6) Minimum Spanning Tree (6) Number - Reach (6) Pattern (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) Algorithm - Brain Teaser (5) Anagram (5) Art Of Programming-July (5) Bellman Ford (5) Big Data (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) Manhattan Distance (5) Matrix Chain Multiplication (5) Maze (5) N Queens (5) Parentheses (5) Quadtrees (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) SPFA(Shortest Path Faster Algorithm) (5) Sieve of Eratosthenes (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5) Anagrams (4) Assumption (4) BFS - Unusual (4) Backtracking-Include vs Exclude (4) Bottom-Up (4) Brute Force - Enumeration (4) Chess Game (4) Consistent Hash (4) DP - 2D (4) DP - Print Solution (4) DP - Two Sequences (4) DP-Include vs Exclude (4) DP-Print Solution (4) Distributed (4) Edit Distance (4) Find Rule (4) Graph - Bipartite (4) Graph - Unusual (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Invariant (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Knight (4) LeetCode - Recursive (4) Limited Range (4) MST (4) Microsoft Interview (4) Multiple DFS (4) Nerd Paradise (4) Normalized Key (4) Online Algorithm (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sort: Index (4) Prime Factor (4) Return Multiple Values (4) Robot (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Symbol Table (4) Tile (4) Triangle (4) Trie - DFS (4) Water Jug (4) algnotes (4) fgdsb (4) 最大化最小值 (4) 树形DP (4) 男人八题 (4) A Star (3) Algorithm Design (3) Approximate Algorithm (3) Augmented BST (3) B Tree (3) BFS - Priority Queue (3) Big Data Algorithm (3) Caterpillar Method (3) Clock (3) Coins (3) Combinatorics (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP - Bit (3) DP - Range (3) DP - Trie (3) DP-Two Variables (3) Dedup (3) Dropbox (3) Easy (3) Enumeration (3) Factor (3) Finite Automata (3) Github (3) GoLang (3) Graph Coloring (3) Greedy - PQ (3) Include vs Exclude (3) Islands (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) Linked List Merge Sort (3) LogN (3) Mark (3) Master Theorem (3) Matrix Exponentiation (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) Negative All Values (3) Parser (3) Pascal's Triangle (3) Pattern Match (3) Programcreek (3) Project Euler (3) Rectangle (3) Recursion (3) Scala (3) SegmentFault (3) Shuffle (3) Skyline (3) Slot (3) Stack - Smart (3) State Machine (3) States (3) Strategy (3) Strongly Connected Components (3) Subtree (3) Trie + DFS (3) Union-Find - Weight (3) With Random Pointer (3) Word Ladder (3) bookkeeping (3) codebytes (3) to-do-2 (3) Activity Selection Problem (2) Advanced Algorithm (2) All Substrings (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) Augmented Tree (2) Auxiliary - Index Map (2) BOJ (2) BT - Path Sum (2) Binary Search - Smart (2) Binomial Coefficient (2) Bipartite (2) Bisection - Index (2) Bit Counting (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Boyer-Moore Voting (2) Branch and Bound Method (2) Cache (2) Candidates (2) Cases (2) Circle - Data (2) Clean Code (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) Custom Sort (2) DP - Binary Search (2) DP - DFS (2) DP - Include vs Exclude (2) DP - O(N) (2) DP - Order (2) DP-3D Table (2) DP-Classical (2) DP-Fill by Length (2) DP-i-k-j (2) Diagonal (2) Distributed Algorithms (2) Doubly Linked List (2) Duplicate (2) Forward && Backward Scan (2) Fraction (2) Function (2) Game (2) GoHired (2) Graham Scan (2) Graph BFS+DFS (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Hard Algorithm (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Iterative (2) K (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) Math-Remainder Queue (2) Matrix Multiplication (2) Matrix Power (2) Meet in the Middle (2) Minimum Vertex Cover (2) Monto Carlo (2) Multiple Steps (2) NP Hard (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Parent-Only Tree (2) Peak (2) PreProcess (2) Programming (2) Range (2) Range Minimum Query (2) Recursion - Review (2) Regular Expression (2) Rejection Sampling (2) Remainder (2) Reuse Forward Backward (2) Reverse Inorder Traversal (2) Rosettacode (2) Search (2) SimHash (2) Simple Algorithm (2) Sparse Table (2) Spatial Index (2) Stack - DFS (2) TV (2) Trailing Zeroes (2) Transform Tree (2) Traversal From End (2) Tree Sum (2) Tree Without Tree Predefined (2) Two Pointers Window (2) Two-End-BFS (2) Union-Find - Unusual (2) Word Break (2) Word Graph (2) Word Trie (2) XOR (2) Yahoo Interview (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) ? (1) Akka (1) Algorithm - New (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) Avoid Duplication Computation (1) BFS - Bit Mask (1) BFS Hard (1) BK-Tree (1) BZOJ (1) Balanced Binary Search Tree (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary String (1) Binary Tree Variant (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Boundary Count (1) Bug (1) Bug Free Code (1) Build Binary Tree (1) BuildIt (1) C/C++ (1) CC Interview (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 - Uber (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Yelp (1) Compression Algorithm (1) Concise (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Cyclic Replacement (1) DFS + RL (1) DFS - Multiple (1) DFS+BFS, Flood Fill (1) DFS-Matrix (1) DI (1) DP - Answer (1) DP - Constant Size (1) DP - How to Update (1) DP - Initialization (1) DP - LIS (1) DP - Last Element (1) DP - Local + Global (1) DP - Monotone Queue Stack (1) DP - PreSort (1) DP - Print All Solution (1) DP - Print All Solutions (1) DP - Prune (1) DP - Push (1) DP - Store all Values (1) DP - Strategy (1) DP - Two Pointers (1) DP - Unusual Process (1) DP -Push (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-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) DP-Slide Window Gap (1) DP-树形 (1) Database (1) Detect Negative Cycle (1) Dictionary (1) Digit (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Dummy (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Forward + Backward Scan (1) Front End Pointers (1) Frontier (1) Funny (1) Fuzzy String Search (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph - Degree (1) Graph - Reverse (1) Graph - Tree (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) Greedy - Hard (1) Guess (1) HOJ (1) Hanoi (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 - Linkedin (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knuth Shuffle (1) Kosaraju’s algorithm (1) Kruskal (1) Kth Element (1) Layers (1) Lazy (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Construction (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode -P (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Lock (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Machine Learning (1) Maintain State (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-Rotate (1) Max Min So Far (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Multi-End BFS (1) Multi-Reverse (1) Multiple Tasks (1) Next Element (1) Next Successor (1) O(N) Hard (1) Offline Algorithm (1) Optimal Play (1) Optimization (1) PAT (1) PQ - MinMax (1) PQ - Multiple (1) Parenthesis (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Pre-Sort - Multiple (1) Prefix Xors (1) Prefixes (1) Probabilistic Data Structure (1) Probability DP (1) Python (1) Queue & Stack (1) RSA (1) Random - Binary Search (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) Remap (1) Resources (1) Return Different Values (1) Reverse - Result (1) Reverse Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Simplify (1) Sort && Binary Search (1) Sort - Counting (1) Space Complexity (1) Square (1) Streaming Algorithm (1) String Algorithm. Symbol Table (1) String Distance (1) SubMatrix (1) Subsequence (1) Substring of Double (1) System of Difference Constraints(差分约束系统) (1) Ternary Search Tree (1) Test (1) Test Cases (1) Thread (1) TimSort (1) Tournament (1) Tournament Tree (1) Trade Off (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie - BFS (1) Trie - DP (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) Unusual (1) UyHiP (1) Valid Tree (1) Vector (1) Virtual Matrix (1) Wiggle Sort (1) Wikipedia (1) ZOJ (1) ZigZag (1) codevs (1) cos126 (1) cycl (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 四边形不等式优化 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 英雄会 (1) 逆向思维 (1)

Popular Posts