题解

  • 5 Longest Palindromic Substring
    • O(n^2) time easy solution.
    • O(nlog(n)) time suffix array.
    • O(nlog(n)) string hash.
  • 6 ZigZag Conversion
  • 8 String to Integer (atoi)
  • 12 Integer to Roman
  • 13 Roman to Integer
    • Scan right to left, keep maximum roman digit accessed, do add or minus according to the maximum.
    • Roman numbers are actually mono stacks.
  • 14 Longest Common Prefix
  • 17 Letter Combinations of a Phone Number
  • 28 Implement strStr()
  • 38 Count and Say
    • 1 -> one one -> 11 -> two one -> 21 -> one two one one -> 1211 -> one one one two two one -> 111221 …
  • 43 Multiply Strings
  • 49 Group Anagrams
    • If word A is word B’s permutation, then they’re anagrams of each other.
  • 58 Length of Last Word
    • Scan from the end.
  • 65 Valid Number
    • First remove space, then check invalid characters, finally sequentially try to grab sign, int, dot, frac and e-num part.
  • 67 Add Binary
  • 68 Text Justification
  • 151 Reverse Words in a String
  • 158 Read N Characters Given Read4 II - Call multiple times
    • Buffer reads in a queue.
  • 161 One Edit Distance
  • 165 Compare Version Numbers
  • 214 Shortest Palindrome
    • Given a string, find minimum length of palindrome formed by adding characters in front of it.
    • KMP, match from tail using head as pattern.
  • 227 Basic Calculator II
    • Evaluate expression without parentheses.
  • 387 First Unique Character in a String
  • 418 Sentence Screen Fitting
    • Similar to text justification. Need to find end-position circles.
  • 459 Repeated Substring Pattern
    • Find whether a string is made up by smaller repeating units.
    • Validate whether s is in (s+s)[1:-1]. This basically checks if the s can be represented by a rotation of itself. If yes, then s is repeated. (GCD-like proof)
    • Use KMP cyclic segment (i - next[i] for 1 <= i <= sLen).
  • 468 Validate IP Address
  • 680 Valid Palindrome II
    • Find whether a string can become a palindrome if at most one character can be deleted.
  • 722 Remove Comments
  • 937 Reorder Log Files
  • 1016 Binary String With Substrings Representing 1 To N
    • Given a 0-1 sequence, find minimum N whose binary representation is not substring of it.
    • Just enumerate all numbers presented in the sequence.