String

  • substring() is O(n)

Palindrome

validate

https://leetcode.com/problems/valid-palindrome/description/ https://leetcode.com/problems/palindrome-partitioning/description/ https://leetcode.com/problems/palindrome-permutation/description/ https://leetcode.com/problems/find-the-closest-palindrome/description/

private boolean isPalindrome(String s, int l, int r) {
    if (l == r) return true;
    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) return false;
        l++;
        r--;
    }
    return true;
}

central extention

key: 1) no need 2d table 2) 2 rounds: 1st round, aba; 2nd round, abba https://leetcode.com/problems/longest-palindromic-substring https://leetcode.com/problems/palindromic-substrings/description/ https://leetcode.com/problems/palindrome-partitioning-ii/description/

// iterate string
for (int i = 0; i < s.length() - 1; i++) {
    expends(s, i, i);
    expends(s, i, i+1);
}
private String expends(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        l--;
        r++;
    }
    return s.substring(l+1, r);
}

dynamic programming

need 2d table https://leetcode.com/problems/longest-palindromic-subsequence/description/ https://leetcode.com/problems/longest-palindromic-substring https://leetcode.com/problems/palindromic-substrings/description/ https://leetcode.com/problems/count-different-palindromic-subsequences/description/ key: 2 pointers

for (int i = 0; i < n; i++) {
    for (int j = i; j >= 0; j--) {
        if (s.charAt(j) == s.charAt(i)) {
            dp[j][i] = j == i || j + 1 == i ? i - j + 1 : 2 + dp[j+1][i-1];
        } else {
            dp[j][i] = Math.max(dp[j+1][i], dp[j][i-1]);
        }
    }
}

anagram/permutation

map char:counts

https://leetcode.com/problems/valid-anagram https://leetcode.com/problems/group-anagrams https://leetcode.com/problems/find-all-anagrams-in-a-string https://leetcode.com/problems/permutation-in-string/description/ https://leetcode.com/problems/find-anagram-mappings

String & word dict

  • lookup words from string in dict:

https://leetcode.com/problems/word-ladder/description/ https://leetcode.com/problems/word-ladder-ii/description/ https://leetcode.com/problems/word-break/description/

  • lookup words from dict in string:

https://leetcode.com/problems/add-bold-tag-in-string/description/

            for (String w : dict) {
                if (s.startsWith(w, i)) {
                    len = Math.max(len, w.length());
                }
            }

Reverse string

toCharArray(), 2 pointers

trick: 1.reverse whole array -> 2. reverse partial array

https://leetcode.com/problems/reverse-words-in-a-string/description/ https://leetcode.com/problems/reverse-words-in-a-string-iii/description/ https://leetcode.com/problems/reverse-words-in-a-string-ii/description/ https://leetcode.com/problems/rotate-array/description/ https://leetcode.com/problems/reverse-vowels-of-a-string/description/ https://leetcode.com/problems/reverse-string-ii/description/ https://leetcode.com/problems/reverse-string/description/

https://jaywinhuang.gitbooks.io/leetcode/content/mySolutions/092-reverse-linked-list-ii.html https://jaywinhuang.gitbooks.io/leetcode/content/mySolutions/151-reverse-words-in-a-string.html https://jaywinhuang.gitbooks.io/leetcode/content/mySolutions/186-reverse-words-in-a-string-ii.html https://jaywinhuang.gitbooks.io/leetcode/content/mySolutions/189-rotate-array.html https://jaywinhuang.gitbooks.io/leetcode/content/mySolutions/206-reverse-linked-list.html

+ - * / operations

Key points: carry curr % 10 curr / 10 Start from right end plus max length max(len1, len2) + 1, multiply max length len1 + len2

https://leetcode.com/problems/add-binary https://leetcode.com/problems/add-two-numbers https://leetcode.com/problems/add-two-numbers-ii/description/ https://leetcode.com/problems/add-strings/description/ https://leetcode.com/problems/plus-one/description/ https://leetcode.com/problems/plus-one-linked-list/description/ https://leetcode.com/problems/multiply-strings

encode/decode/calculator

stack iterative and recursion thing in a parenthesis is a new recursion

https://leetcode.com/problems/decode-string https://leetcode.com/problems/number-of-atoms/description/ https://leetcode.com/problems/expression-add-operators/description/ https://leetcode.com/problems/evaluate-reverse-polish-notation/description/ https://leetcode.com/problems/parse-lisp-expression https://leetcode.com/problems/basic-calculator/description/

brute force

https://leetcode.com/problems/integer-to-roman/discuss/6274/Simple-Solution https://leetcode.com/problems/integer-to-english-words

word pattern

map+set https://leetcode.com/problems/isomorphic-strings/description/ https://leetcode.com/problems/word-pattern https://leetcode.com/problems/word-pattern-ii/description/

Word abbreviation

https://leetcode.com/problems/unique-word-abbreviation https://leetcode.com/problems/generalized-abbreviation https://leetcode.com/problems/valid-word-abbreviation https://leetcode.com/problems/minimum-unique-word-abbreviation https://leetcode.com/problems/word-abbreviation

Calculator / evaluate expression

PreviousEdge cases - input validationNextArray

Last updated