0. Space Replacement.java Level: Medium Tags: [String]

1. Judge Route Circle.java Level: Easy Tags: [String]

简单的character checking. 各个方向, 加加减减.

2. Reverse Vowels of a String.java Level: Easy Tags: [String, Two Pointers]

vowels: 元音字母. 要求reverse所有元音字母.

• 前后两个指针, 在while loop里面跑.
• 注意 i<j, 一旦相遇, 就break.
• 找到合适的, 就做swap.
• StringBuffer可以 sb.setCharAt()记得用.
• O(n)

拿出所有vowels, 反过来放进去. O(n)

3. Scramble String.java Level: Hard Tags: [DP, Interval DP, String]

• 给两个string S, T. 检验他们是不是scramble string.
• scramble string 定义: string可以被分拆成binary tree的形式, 也就是切割成substring;
• 旋转了不是leaf的node之后, 形成新的substring, 这就是原来string的 scramble.

• 降维打击, 分割, 按照长度来dp.
• dp[i][j][k]: 数组S从index i 开始, T从index j 开始, 长度为k的子串, 是否为scramble string

• 一切两半以后, 看两种情况: , 或者不rotate这两半. 对于这些substring, 各自验证他们是否scramble.
• 不rotate分割的两半: S[part1] 对应 T[part1] && S[part2] 对应 T[part2].
• rotate分割的两半: S[part1] 对应 T[part2] && S[part2] 对应 T[part1].

• len == 1的时候, 其实无法旋转, 也就是看S,T的相对应的index是否字符相等.
• initialization非常非常重要. 很神奇, 这个initailization 打好了DP的基础, 后面一蹴而就, 用数学表达式就算出了结果.
• input s1, s2 在整个题目的主要内容里面, 几乎没有用到, 只是用在initialization时候.
• More details, 看解答

4. Interleaving String.java Level: Hard Tags: [DP, String]

双序列DP, 从最后点考虑. 拆分问题的末尾, 考虑和s1, s2 subsequence之间的关联.

求存在性, boolean

5. Letter Combinations of a Phone Number.java Level: Medium Tags: [Backtracking, String]

方法1: Iterative with BFS using queue.

方法2: Recursively adding chars per digit

6. Edit Distance.java Level: Hard Tags: [DP, Double Sequence DP, Sequence DP, String]

time: O(MN) Space: O(N)

两个字符串, A要变成B, 可以 insert/delete/replace, 找最小变化operation count

• 考虑两个字符串的末尾index� s[i], t[j]: 如果需要让这两个字符一样, 可能使用题目给出的三种operation: insert/delete/replace?
• 先calculate最坏的情况, 3种operation count + 1; 然后在比较match的情况.
• 注意, 在i或者j为0的时候, 变成另外一个数字的steps只能是全变.
• 第一步, 空间时间都是O(MN), O(MN)
• 滚动数组优化, 空间O(N)

• insert: assume insert on s, �#ofOperation = (s[0 ~ i] to t[0 ~ j-1]) + 1;
• delete: assume delete on t, #ofOperatoin = (s[0 ~ i - 1] to t[0 ~ j]) + 1;
• replace: replace both s and t, #ofOperatoin = (s[0 ~ i - 1] to t[0 ~ j - 1]) + 1;
• dp[i][j]�代表了两个 sequence 互相之间的性质: �s[0 ~ i] �转换成 s[0~j] 所需要的最少 operation count
• init: 当i==0, dp[0][j] = j; �每次都要 + j 个character; 同理, 当j==0, dp[i][0] = i;
• 而dp[i][j]有两种情况处理: s[i] == t[j] or s[i] != t[j]

• 这种判断取决于经验: 如果知道initialization可以再 double for loop 里面一起做, 那么可以留着那么做
• 这样属于 需要什么, initialize什么
• 事后在做space optimization的时候, 可以轻易在 1st dimension 上做rolling array

• 可以做, 但是不建议:这道题需要找 min count, 而不是search/find all solutions, 所以search会写的比较复杂, 牛刀杀鸡.

7. Distinct Subsequences.java Level: Hard Tags: [DP, String]

Double Sequence DP: 0. DP size (n+1): 找前nth的结果, 那么dp array就需要开n+1, 因为结尾要return dp[n][m]

1. 在for loop 里面initialize dp[0][j] dp[i][0]
2. Rolling array 优化成O(N): 如果dp[i][j]在for loop里面, 就很好替换 curr/prev

8. Longest Substring Without Repeating Characters.java Level: Medium Tags: [Hash Table, String, Two Pointers]

方法1: Two Pointers 双指针: 从start开始遍历, 但是第一步是while loop来推进end; 直到推不动end, 然后start++ 巧妙点: 因为end是外围variable, 在start的loop上, end不会重置;[star ~ end] 中间不需要重复计算. 最终可以O(n);

Previous verison of two pointers: 用两个pointer, head和i. 注意：head很可能被退回到很早的地方，比如abbbbbba,当遇到第二个a，head竟然变成了 head = 0+1 = 1.
当然这是不对的，所以head要确保一直增长，不回溯

方法2: HashMap<Char, Integer>: <character, last occurance index> 一旦有重复, rest map. 没有重复时候, 不断map.put(), 然后求max值

问题: 每次reset map之后就开始从新从一个最早的index计算, 最坏情况是O(n^2): 'abcdef....xyza'

9. Minimum Window Substring.java Level: Hard Tags: [Hash Table, String, Two Pointers]

基本思想: 用个char[]存string的frequency. 然后2pointer, end走到底, 不断validate. 符合的就process as result candidate.

HashMap的做法比char[]写起来要复杂一点, 但是更generic

10. Longest Substring with At Most K Distinct Characters.java Level: Hard Tags: [Hash Table, Sliding Window, String]

大清洗 O(nk)
map.size一旦>k，要把longest string最开头（marked by pointer:start）的那个char抹掉
一旦某一个char要被清除，所以在这个char 的1st and last appearance之间的char都要被清洗from map

11. Palindrome Pairs.java Level: Hard Tags: [Hash Table, String, Trie]

Obvious的做法是全部试一遍, 判断, 变成 O(n^2) * O(m) = O(mn^2). O(m): isPalindrome() time.

当然不行了, 那就看是O(nlogN), 还是O(n)?

O(mn)

• 每一个word, 都可以拆分成 front + mid + end. 如果这个word + 其他word可以组成palindrome,那就是说
• 砍掉 (mid+end), front.reverse() 应该存在 words[] 里面.
• 砍掉 (front+mid), end.reverse() 应该存在 words[] 里面.
• 我们用HashMap存所有的<word, index>, 然后reverse, 找配对就好.

• 如果有 empty string "", 那么它跟任何一个palindrome word, 都可以配对, 并且根据位置前后变换, 凑成2份 distinct indexes.
• 这样就有了那个 if (reverseEnd.equals("")) {...} 的logic.
• 注意: 虽然在处理砍头/砍尾的两个 for loop里面都在根据 empty string 重复记录, 但因为 "" 自己本身不能作为起点, 所以overall只会在被其他palindrome配对时记录一次.

还要做一下那.

12. Change to Anagram.java Level: Easy Tags: [String]

HackerRank里面的random 题目: 给一个string, 一切成两半, 看两半要变化多少个字符, 能变成anagram.

• 切两半成两个String A,B. 分别在int count[26]里面++, --.

• 记录 26个小写字母的频率. 如果全部抵消, 就是anagram.

• 注意: 最后count出来要除以2：字母不同，会在不同的字母位上加减count,那么就是刚好重复计算了一遍。所以除以二

• Note: HackerRank里要注意自己写: Scanner, import java.util, non-static method ...etc.

13. Compare Version Numbers.java Level: Medium Tags: [String]

给两串version number, 由数字和'.' 组成. 比较先后顺序.

If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

• 用 str.split("\.") 分割string
• Convert成integer, 逐个击破

• '1.0' 和 '0' 是相等的
• 如果可以假设version integer都是valid, 直接Integer.parseInt()就可以了
• 不然的话, 可以compare string

14. Compare Strings.java Level: Easy Tags: [String]

看StringA是不是包括所有 StringB的字符.

• 比较一下大小, null.
• 然后用int[]来count chars from A, count[x]++. 再对照chars in B, count[x]--
• 如果 count[c] < 0, 就 false.
• O(n)

15. Count and Say.java Level: Easy Tags: [Basic Implementation, String]

介绍一种count数字的方法, 然后每一行读出上一行的结果, 一行一行推算. 问nth行是啥样?

• 主要是题意很难理解, 非常misleading, 等到看明白题目, 其实没有什么算法要求.
• Count duplicates and print

16. Decode Ways.java Level: Medium Tags: [DP, Partition DP, String]

time: O(n) space: O(n)

给出一串数字, 要翻译(decode)成英文字母. [1 ~ 26] 对应相对的英文字母. 求有多少种方法可以decode.

• 加法原理: 根据题意, 有 range = 1 的 [1, 9], range = 2 的 [10~26] 来作为partition.
• 确定末尾的2种状态: single letter or combos. 然后计算出单个letter的情况, 和双数的情况
• 定义dp[i] = 前i个digits最多有多少种decode的方法. new dp[n + 1].
• 加法原理: 把不同的情况, single-digit, double-digit 的情况加起来
• dp[i] += dp[i - x], where x = 1, 2
• note: calculate number from characters, need to - '0' to get the correct integer mapping.
• 注意: check value != '0', 因为'0' 不在条件之中(A-Z)
• Space, Time O(n)

• 这里只有两种partition的情况 range=1, range =2. 如果有更多partition的种类, 就可能多一层for loop做循环

17. Group Anagrams.java Level: Medium Tags: [Hash Table, String]

给一串string, return list of list, 把anagram 放在一起.

• 存anagram
• 用 character frequency 来做unique key
• 用固定长度的char[26] arr 存每个字母的frequency; 然后再 new string(arr).
• 因为每个位子上的frequency的变化，就能构建一个unique的string
• O(nk), k = max word length

• 和check anagram 想法一样：转化并sort char array，用来作为key。
• 把所有anagram 存在一起。注意结尾Collections.sort().
• O(NKlog(K)), N = string[] length, k = longest word length

18. Flip Game.java Level: Easy Tags: [String]

• 可以用 sb.replace(i, j, "replacement string")
• 简单按 window=2 来扫描
• 原来只需要从'++'转到'--'的情况
• O(n)

19. Implement strStr().java Level: Easy Tags: [String, Two Pointers]

给两个string A, B, 找一个 B 在 A 种的起始位置.

• 找到B在A中的起始位置, 然后看一下从这个点开始的substring是否等于B就可以了
• 还挺多坑的, 这些可以帮助优化:
• 1. 当B是“”的时候，也就是能在A的其实位置找到B....index = 0.
• 2. edge condition: 如果 haystack.length() < needle.length() 的话, 必须错, return -1
• 3. 如果在某个index, A后面剩下的长度, 比B的长度短, 也是误解, return -1

20. Length of Last Word.java Level: Easy Tags: [String]

给一个String, 里面有lower case character 和 ' '. 找最后一个单个word的长度

• 从末尾找' ', 找到了计算长度
• 记得要s.trim(), 把首尾的space去掉

21. Longest Common Substring.java Level: Medium Tags: [DP, Double Sequence DP, Sequence DP, String]

• 两个string, 找最值: longest common string length
• 序列型, 并且是双序列, 找两个序列 (两维的某种性质)
• dp[i][j]: 对于 A 的前i个字母, 对于 B 的前j个字母, 找最长公共substring的长度
• dp = new int[m + 1][n + 1]
• dp[i][j] = dp[i - 1][j - 1] + 1; only if A.charAt(i - 1) == B.charAt(j - 1)
• 注意track max, 最后return
• space O(n^2), time(n^2)

• 空间优化, [i] 只有和 [i - 1] 相关, 空间优化成 O(n)

• 找所有A的substring, 然后B.contains()
• track max substring length
• O(n^2) time

22. Valid Palindrome.java Level: Easy Tags: [String, Two Pointers]

验证string是不是 palindrome. 只考虑 alphanumeric, 其他字符可以忽略

• 前后两个指针, 往中间移动, 查看是否字母重合

• 可以用 ASCII code 来手动过滤, 只要 '0' ~ '9', 'a' ~ 'z', 'A' - 'Z' 之间的
• 也可以用 regular expression: match 所有这些字母, 是 [a-zA-Z0-9]
• 那凡是不是这些字母的 match, 就是取反: "[^a-zA-Z0-9]". 测试: https://regex101.com/

23. Rotate String.java Level: Easy Tags: [String]

给两个String, 看A rotate之后 能不能变成B

• Basics
• StringBuffer.deleteCharAt(xx), StringBuffer.append(xx)
• O(n)

• Different problem: 给一个char[], 要rotate offset times.
• 三步rotate
• 有个坑：offset可能很长，那么要%length，才能得到真正需要rotate的部分。
• Note: rotate 一个 full length之后，是string 不变

24. Next Closest Time.java Level: Medium Tags: [Basic Implementation, Enumeration, String]

给一个时间string"12:09", 用里面的4个integer组合成其他时间string, 目标找最小的next time.

如果组合出的time string 在input time之前, 默认 + 24 hours.

• enumerate all candidates and filter to keep the correct ones
• String.compareTo(string) -> gives lexicographical comparision

25. Encode and Decode Strings.java Level: Medium Tags: [String]

如题.

• 'word.length()#word' 这样encode, 可以避免遇到#
• 基于我们自己定的规律, 在decode的里面不需要过多地去check error input, assume所有input都是规范的.
• decode就是找"#",然后用"#"前的数字截取后面的string.

26. Longest Common Prefix.java Level: Easy Tags: [String]

找一串String里面最长的公共prefix.

• Sort O(nlogn)
• first and last string should share common prefix
• 这里假设题目要求的是所有string的公共 prefix, 而不是部分strings

• Nested loop, 每一次比较所有string 同位是否相等
• 相等，append string. 不等，return.
• O(mn)

27. Restore IP Addresses.java Level: Medium Tags: [Backtracking, DFS, String]

给一串数字, 检查是否是valid IP, 如果合理, 给出所有valid 的IP组合方式.

• 递归的终点:list.zie() == 3, 解决最后一段
• 递归在一个index上面, pass s.toCharArray()
• validate string要注意leading '0'
• 注意: 递归的时候可以用一个start/level/index来跑路
• 但是尽量不要去改变Input source， 会变得非常confusing.
• note: code有点messy, 因为要考虑IP的valid情况
• 那个'remainValid', 其实是一个对于remain substring的判断优化, 不成立的就不dfs了

28. Reverse Words in a String.java Level: Medium Tags: [String]

• 结尾不能有空格
• trim() output
• 如果Input是 ""的话，split以后就啥也没有了
• 另个题目Reverse Words in String (char[]) 可以in-place, 条件是char[]里面是没有首尾空格.
• Time, Space: O(n)

• flip entire string, then flip each individual string (代码有点多, 这道题犯不着)

29. Reverse Words in a String II.java Level: Medium Tags: [String]

• reverse用两回. 全局reverse。局部:遇到空格reverse
• 注意ending index: i == str.length - 1, 结尾点即使没有' '也要给reverse一下最后一个词

30. Reverse Words in a String III.java Level: Easy Tags: [String]

给一个String, 里面的Word被single space split开来, 目的是reverse里面所有的Word, 但preserve Word 和 space order.

• Reverse Words in a String II 的降级版, 去掉第一个overall reverse就好了

31. Expression Add Operators.java Level: Hard Tags: [Backtracking, DFS, Divide and Conquer, String]

给一个数字String, 数字来自0-9, 给3个操作符 +,-,*, 看如何拼凑, 可以做出结果target.

output 所有 expression

• 跟string相关, 写起来可能稍微繁琐一点
• 数字有 dfs([1,2,3...]) 组合方法
• operator有[+,-,*] 3种组合方法
• 注意1: 乘号要特殊处理, pass along 连乘的数字, 计算下一步乘积的时候, 要 sum - preProduct + product
• 注意2: '01' 这种数字要skip
• 注意3: 第一个选中数字不需要加操作符, 直接加进去
• Time: O(4^n)， Space: O(4^n)
• T(n) = 3 * T(n-1) + 3 * T(n-2) + 3 * T(n-3) + ... + 3 *T(1);
• T(n-1) = 3 * T(n-2) + 3 * T(n-3) + ... 3 * T(1);
• Thus T(n) = 4T(n-1) = 4^2 * T(n - 1) = .... O(4^n)

• 逻辑一样, 代码更短, 只不过不做list, 直接pass buffer + "+" + curr
• 因为每次都创建新string, 所以速度稍微慢一点. Time complexity 一样

32. Shortest Palindrome.java Level: Hard Tags: [KMP, String]

• check (mid, mid+1), or (mid-1, mid+1).
• If the two position matches, that is a palindrome candidate
• 比较front string 是否是 end string 的substring
• O(n^2)
• timeout on last case: ["aaaaaa....aaaacdaaa...aaaaaa"]

• TODO

33. Generate Parentheses.java Level: Medium Tags: [Backtracking, DFS, Sequence DFS, String]

• start with empty string, need to go top->bottom
• 取或者不取(, )
• rule: open parentheses >= close parentheses
• Note: 在DFS时 pass a reference (StringBuffer) and maintain, instead of passing object (String) and re-create every time
• time: O(2^n), pick/not pick, the decision repat for all nodes at every level
• T(n) = 2 * T(n - 1) + O(1)

• figure out n=1, n=2 => build n=3, and n=4
• dfs(n-1) return a list of candidates
• add a pair of () to the candidates: either in front, at end, or contain the candidates

34. Binary Representation.java Level: Hard Tags: [Bit Manipulation, String]

• 首先要分两半解决，断点是'.': str.split("\.");
• Integer那一半好弄，whie loop里: num%2, num/2. 做一个 parseInteger() function
• Decimal那边复杂点. 做一个 parseDecimal() function:
• bit == 1的数学条件: 当下num * 2 >= 1。 更新: num = num * 2 - 1;
• bit == 0的数学条件: num * 2 < 1. 更新: num = num * 2

• num是 double, 小数在 num = num * 2 - 1 的公式下可能无限循环
• 因此check: num重复性，以及binary code < 32 bit.
• 所以题目也才有了32BIT的要求!

35. Longest Palindromic Substring.java Level: Medium Tags: [DP, String]

给一个string, 找到最长的palindrome substring.

Related: Longest Palindromic Subsequence, Palindrome Partioning II

O(n^2) is not too hard to think of. How about O(n)?

• 从中间劈开, 遍历i: 从n个不同的点劈开: 每次劈开都看是否可以从劈开出作为palindromic的中点延伸
• palindrome两种情况: odd, even palindrome
• Worst case: 整个string都是相同字符，time complexity变成： 1 + 2 +３　＋　．．．　＋n = O(n^2)

• 穷举double for loop. O(n^2)
• boolean isPalin[i][j], 每次确认有palindrome就记录下来true / false
• 穷举的for loop计算顺序: end point j, and stat point i = [0, j]
• 在计算 isPalin[i][j]的时候, isPalin[i+1][j-1]应该已经计算过了.
• double for loop: O(n^2). slower, because it guarantees O(n^2) due to the for loop

• TODO
• https://www.felix021.com/blog/read.php?2040

36. Longest Valid Parentheses.java Level: Hard Tags: [Coordinate DP, Stack, String]

给一串string, 里面只有(, ). 找最长valid parentheses 的长度.

• use dp[i] track local max, maintain global max
• int[] dp. dp[i]: longest valid string that ends on i.
• 结尾是 ')', 2种情况: 1. 刚好s[i-1]是'('; 2. s[i]的')'更前面的一个起始'(' 对应
• 注意, 结尾如果是'('属于不合理情况, 忽略.
• init: dp[0] = 0, 单个char不可能成型.
• 计算顺序: 从左到右, 找local max, maintain global max
• O(n) space, O(n) runtime

• Stack 里面存所有的open/close parentheses.
• 如果遇到stack.top()刚好开合结掉, 就stack.pop().
• 剩下的都是不合理的elements.
• 有点像negatively找 solution: endIndex - 最后一个failedIndex(stack.pop()) - 1, 应该就是最后一个succeeded string的长度
• 每次更新 endIndex 为stack.top(), 然后从stack继续找下一个failedIndex
• 所有的length作比较, 就可以找出最长length
• O(n) stack space, O(n) runtime. 应该比dp慢一点, 因为做了2遍O(n)

37. Sort Letters by Case.java Level: Medium Tags: [Partition, Sort, String, Two Pointers]

给一串字符(ASCII 大写, 小写字母), 要求sort 小写字母, 在大写字母前面.

字母间的前后顺序无所谓, 也不需要preserve original order .

跟sort color分成相似.

• 其实就是quick sort里面的partition function的简化版
• Two pointers, 找一个 pivot 'a' 来区分大写小写字母
• ASCII code 里面 大写字母在小写字母前面, 数字更小
• 然后 while, move start++, end--,
• 每一轮都swap

• 直接用两个 pointer left/right 标记开头结尾
• 每次遇到 >= 'a' 就是小写字母, swap(chars, i, left);
• 每次遇到 < 'a' 就是大写字母, swap(chars, i, right);
• 注意: 每次处理完left swap, 任由for loop i++, 因为确定 [0 left] 都是准确的
• 每次处理完 right swap, 我们不确定从 right index 换过来的是不是正确的, 所以 i--, 跟for loop 的 i++抵消.
• 写 while loop 的 solution看起来更容易理解.

38. Longest Words.java Level: Easy Tags: [Hash Table, String]

给一串String, 找到最长的长度, 把最长的String全都return

• <Integer,List>
• 存最长值, 最后map.get(max)

39. Unique Characters.java Level: Easy Tags: [Array, String]

determine if characters are unique in string

• space O(n), time O(n)

• space O(n), time O(nlogn)

• double for loop: O(n^2)

40. Palindromic Substrings.java Level: Medium Tags: [DP, String]

根据题意, count # of palindromic substring. (不同index截取出来的substring算不同的情况)

• build boolean[][] to check isPalin[i][j] with DP concept
• �check all candidates isPalin[][]
• O(n^2)

https://leetcode.com/problems/palindromic-substrings/discuss/105689/Java-solution-8-lines-extendPalindrome

41. Multiply Strings.java Level: Medium Tags: [Math, String]

给两个integer String, 求乘积

• let num1 = multipier, num2 = base.
• mutiply and save into int[m + n], without carry. Loop over num1, each row num1[x] * num2
• move carry to the correct index and direclty save result
• calculate carry on rst[]: sb.insert(0, c) such that no need to reverse() later
• remove leading '0', but do not delete string "0"
• time,space O(mn)

• Bad solution: reversing makes it complicated, no need to reverse.
• 1. 数字‘123’， 在数组里面， index == 0 是 ‘1’。 但是我们平时习惯从最小位数开始乘积，就是末尾的'3'开始。
• 所以！翻转两个数字先！我去。这个是个大坑。
• 2. 乘积product，和移动Carrier都很普通。
• 3. ！！最后不能忘了再翻转。
• 4. 最后一个看坑。要是乘积是0，就返回‘0’。 但是这个其实可以在开头catch到没必要做到结尾catch。
• 用到几个StringBuffer的好东西: reverse(), sb.deleteCharAt(i)
• 找数字，或者26个字母，都可以: s.charAt(i) - '0'; s.charAt(i) - 'a';

42. Simplify Path.java Level: Medium Tags: [Stack, String]

time: O(n) space: O(n)

给一个path, simplify成最简单形式. 注意考虑edge case

• 理解unix path 的情况, 不懂得要问:
• 1. . 代表current directory, 可以忽略.
• 2. ../ 表示previous level.
• 3. double slash 可以忽略.
• 4. empty string 要output /
• 最终就是用stack (上一个加进去的item, 用来备选pop() out), 遇到 ../ pop()掉上一个加上去的item, 其余加进stack
• 最终用 '/' 把所有item连接起来.

43. Valid Number.java Level: Hard Tags: [Enumeration, Math, String]

time: O(n)

分析edge case, 和各种情况, 然后判别是否是valid number

• 遇到 ., e, +/-, int的几种不同情况
• 分别遇到的顺序不同时候, 结果也不同.
• 这道题更多是分析情况, 然后把edge case enumerate出来, 算法的意义比较少.

44. Read N Characters Given Read4.java Level: Easy Tags: [Enumeration, String]

Read4 题目. 理解题目: 是有个input object buff, 会被populated with data.

• 理解题目: 其实就是track 可以read多少bytes by read4() response
• 另外一个有用的function System.arraycopy(src, srcIndex, dest, destIndex, length)

45. Integer to English Words.java Level: Hard Tags: [Enumeration, Math, String]

给一个小于 Integer.MAX_VALUE (2^31 - 1) 的数字, 转换成英语. (不需要加 'and')

• 基本implementation
• 分类讨论: thounsand, million, billion. 3个数字一格.
• 用array枚举 token
• 运用 % 和 / 来找到每个分段的英语翻译
• 3-digit 的部分, 可以用一个helper funtion来找到结果, 每段的处理方法都是一样的

• StringBuffer 更有效率! sb.insert(0, xxx) append在sb前面
• 注意加 " " 的时候, 如果多余, 要trim()
• 注意, 小于20的数字, 有自己的特殊写法, 需要额外handle
• 这道题目就是要细致耐心, 几乎么有什么算法, 就是想要写的efficient并且正确, 需要很小心

46. Valid Palindrome II.java Level: Easy Tags: [String]

• delete an index = jump over the index
• 注意 boolean chance 可以用一个helper function

47. Word Ladder II.java Level: Hard Tags: [Array, BFS, Backtracking, DFS, Hash Table, String]

给一串string, start word, end word. 找到所有从 startWord -> endWord的最短路径list.

变化方式: mutate 1 letter at a time.

• 用BFS找最短路径.
• 问题: how to effectively store the path, if the number of paths are really large?
• If we store Queue<List>: all possibilities will very large and not maintainable
• 用BFS做出一个反向structure, 然后再reverse search

• BFS 找到所有start string 可以走到的地方 s, 放在一个overall structure里面: 注意, 存的方式 Map<s, list of sources>
• BFS时候每次都变化1step, 所以记录一次distance, 其实就是最短路径candidate (止步于此)
• 1. 反向mutation map: destination/end string -> all source candidates using queue: Mutation Map
• Mutation Map<s, List>: list possible source strings to mutate into target key string.
• 2. 反向distance map: destination/end string -> shortest distance to reach dest
• Distance Map<s, possible/shortest distance>: shortest distance from to mutate into target key string.
• BFS prep step 并没解决问题, 甚至都没有用到end string. 我们要用BFS建成的反向mapping structure, 做search

• 从结尾end string 开始扫, 找所有可以reach的candidate && only visit candidate that is 1 step away
• dfs 直到找到start string.

• reversed structure 已经做好了, 现在做search 就可以: 也可以选用bfs.
• Queue<List<String>> to store candidates, searching from end-> start

48. Text Justification.java Level: Hard Tags: [Enumeration, String]

按照规则 adjust text. 就是Word里面: 有一行太长, adjust word 中间的space, 然后保证每一行的total width 顶格.

还有一些细节规则, 看原题

• Summing space = width + (size-1). maintain: 1. list of candidates, 2. width of actual words
• calculate space in between: remain/(size - 1)
• overall for loop; clean up list: 1. over size; 2. last item
• 一点也不难, 但是要小心: deal with list of string的时候, 注意处理干净sum size of list, 就行了.
• 干净处理space: 只处理 (n-1) items, 然后最后一个拿到for loop 外面, 特殊处理.

• Clarification, observation:
• can start with greedy approach to stack as many words as possible
• once exceed the length, pop the top, and justify the added words (untouched words tracked by index)
• left justify: given list/stack of words with size t, overall remaining space length m,
• deal with last line with special care: just fill one space, and fill the rest of the row with space
• Does not seem very complicated, but need additional care of calculating the amount of space needed.
• Overall runtime: O(n) to go over all space
• Overall space O(maxWidth) for maxWidth amount of strings

49. Read N Characters Given Read4 II - Call multiple times.java Level: Hard Tags: [Enumeration, String]

Read N Character using Read4(char[] buf) 的加强版: 可以不断读 read(buf, n)

• 注意String的index handle, 慢慢写edge case
• 理解题目意思: read4(char[] buf) 这样的 populate input object 的function稍微少一点.
• 遇到时候, 仔细理解function用法, 不要慌乱. 其实思考方式很简单, 仔细handle string 还有 edge case就好了.

50. Longest Substring with At Most Two Distinct Characters.java Level: Hard Tags: [Hash Table, Sliding Window, String, Two Pointers]

如题.

• 原本想用 DP, 但是其实用 sliding window 的思想
• sliding window 的切割: 用hashmap 存 last occurrance of char index;
• map.remove(c) 之后, 就等于彻底切掉了那一段; 那么 map.get(c) + 1 也就是新的 left window border

51. String to Integer (atoi).java Level: Medium Tags: [Math, String]

• check sign, leading-0, overall size > 11, check max/min in Long format
• if passed all tests, parseInt()

• if (!str.matches("[+-]?(?:\d+(?:\.\d*)?|\.\d+)")). 猛了一点

52. Roman to Integer.java Level: Easy Tags: [Math, String]

• 熟悉罗马字母规则
• 1. 'I V X L C D M' 分别代表的数字
• 2. 列举combo的情况，需要从原sum里面减掉多加的部分: 'IV, IX'减2, 'XL, XC'减20, 'CD, CM'减200.
• Leading I(1*2), X(10*2), C(100*2) causes double counting

https://en.wikipedia.org/wiki/Roman_numerals

53. Valid Parentheses.java Level: Easy Tags: [Stack, String]

剥皮过程。解铃还须系铃人
左边的外皮'{['在stack底部
右边的外皮应该和stack顶上的左外皮一一对应

54. First Unique Character in a String.java Level: Easy Tags: [Hash Table, String]

方法1: 按照题意, 找到第一个 first index == last index的字母.

方法2: 用hashmap存字母的index, 有些重复字母的index就会是个list. 找到单一index, 结合成list, sort, return list.get(0)

55. Add Binary.java Level: Easy Tags: [Math, String, Two Pointers]

• Use two pointers i, j to track the 2 strings
• Add when i and j are applicable. While (i >= 0 || j >= 0)
• StringBuffer.insert(0, x);
• handle carry

• 土办法没技术，把binary换成数字，加起来，再换成binary
• 如果input很大，那么很可能int,long都hold不住。不保险。

56. One Edit Distance.java Level: Medium Tags: [String]

如果S, T只用一个operation就能变成相等, return true.

• 换完之后，理论上换成的String 就应该全等
• for loop, 一旦找到不一样的char, 就判断那三种可能性: insert/delete/replace
• insert/delete 对于2个string来说, 效果是类似的
• O(n)

57. Group Shifted Strings.java Level: Medium Tags: [Hash Table, String]

• shit by offset. int offset = s.charAt(0) - 'a';
• increase if less than 'a': if (newChar < 'a') newChar += 26;

• 相同shift规则的string, 能被推算到同一个零起始点，就是共同减去一个char,最后就相等。以此作为key，用HashMap。一目了然。
• 记得根据题目意思，一开始要String[] sort一下。

58. Regular Expression Matching.java Level: Hard Tags: [Backtracking, DP, Double Sequence DP, Sequence DP, String]

跟WildCard Matching 一样, 分清楚情况讨论 string p last char is '' 还有并不是 ''

这里的区别是, '*' 需要有一个preceding element, 那么:

• repeat 0 times
• repeat 1 times: need s[i-1] match with prior char p[i-2]

59. Wildcard Matching.java Level: Hard Tags: [Backtracking, DP, Double Sequence DP, Greedy, Sequence DP, String]

Double sequence DP. 与regular expression 很像.

• 分析字符 ?, * 所代表的真正意义, 然后写出表达式.
• 搞清楚initialization 的时候 dp[i][0] 应该always false. 当p为empty string, 无论如何都match不了 (除非s="" as well)
• 同时 dp[0][j]不一定是false. 比如s="",p="*" 就是一个matching.
• A. p[j] != '*'
  1. last index match => dp[i - 1][j - 1]
  2. last index == ? => dp[i - 1][j - 1]
• B. p[j] == "*"
  1. • is empty => dp[i][j - 1]
  2. • match 1 or more chars => dp[i - 1][j]