# 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/>

```java
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/>

```java
// 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

```java
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/>

```java
            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

* [0282. Expression Add Operators](https://github.com/jaywinhuang/leetcode/blob/master/topics/0282-expression-add-operators.md)
* [0224. Basic Calculator](https://github.com/jaywinhuang/leetcode/blob/master/topics/0224-basic-calculator.md)
* [0227. Basic Calculator II](https://github.com/jaywinhuang/leetcode/blob/master/topics/0227-basic-calculator-ii.md)
* [0770. Basic Calculator IV](https://github.com/jaywinhuang/leetcode/blob/master/topics/0770-basic-calculator-iv.md)
* [0772. Basic Calculator III](https://github.com/jaywinhuang/leetcode/blob/master/topics/0772-basic-calculator-iii.md)
* [0736. Parse Lisp Expression](https://github.com/jaywinhuang/leetcode/blob/master/topics/0736-parse-lisp-expression.md)
* [0439. Ternary Expression Parser](https://github.com/jaywinhuang/leetcode/blob/master/topics/0439-ternary-expression-parser.md)