🍎
Leetcode
  • README
  • Templates
    • interview_checklist
    • 🥰beauty of python
    • online IDE templates
    • time complexity analysis
  • Data structures
    • bit_operation
    • deque
    • hashtable
    • linked_list
    • priority_queue
      • Arrangement
      • Sort+PQ
    • stack
    • string
    • intervals
    • trie
    • graph
    • tree
  • Algorithm
    • bfs
    • binary_search
    • dfs
    • topological sort
    • dynamic_programming
    • greedy
    • union_find
    • recursion
    • two_pointers
    • Offline processing
  • Other
    • design
    • everything
    • math
  • Company
    • Tree
    • BinarySearch
Powered by GitBook
On this page
  • String
  • Rolling Hash
  • KMP
  • Manacher
  • Palindrome
  • 833. Find And Replace in String
  1. Data structures

string

  • String

    • Rolling Hash

    • KMP

    • Manacher

    • Palindrome

    • 833. Find And Replace in String

String

006.ZigZag-Conversion (M+) 336.Palindrome-Pairs (H-) 388.Longest-Absolute-File-Path (M+) 408.Valid-Word-Abbreviation (M) 411.Minimum-Unique-Word-Abbreviation (H) 418.Sentence-Screen-Fitting (M+) 423.Reconstruct-Original-Digits-from-English (H-) 527.Word-Abbreviation (M+) 556.Next Greater Element III (H-) 616.Add-Bold-Tag-in-String (M) 467.Unique-Substrings-in-Wraparound-String (H-) 564.Find-the-Closest-Palindrome (H) 722.Remove-Comments (H) 736.Parse-Lisp-Expression (H-) 816.Ambiguous-Coordinates (M+) 844.Backspace-String-Compare (M+) 1616.Split-Two-Strings-to-Make-Palindrome (M+) 1754.Largest-Merge-Of-Two-Strings (M+) 1849.Splitting-a-String-Into-Descending-Consecutive-Values (M+)

Rolling Hash

1044.Longest-Duplicate-Substring (H) 1062.Longest-Repeating-Substring (H-) 1554.Strings-Differ-by-One-Character (H) 1698.Number-of-Distinct-Substrings-in-a-String (H-) 1923.Longest-Common-Subpath (H)

KMP

1392.Longest-Happy-Prefix (H) 028.Implement-strStr (H) 214.Shortest-Palindrome (H) 459.Repeated-Substring-Pattern (H) 572.Subtree-of-Another-Tree (H) 1367.Linked-List-in-Binary-Tree (H) 1397.Find All Good Strings (TBD) 1764.Form-Array-by-Concatenating-Subarrays-of-Another-Array (H)

Manacher

005.Longest-Palindromic-Substring (H) 214.Shortest-Palindrome (H) 647.Palindromic-Substrings (M+) 1960.Maximum-Product-of-the-Length-of-Two-Palindromic-Substrings (H)

Palindrome

  • Several ways to solve the Longest palindrome substring problem

    • DP-based solution: O(n^2) space and time, if need to storing palindrome result, this is always better (e.g. palindrome partitioning)

    • Start looping from middle: O(n^2) time

    • Manacher's algorithm: O(n) time, not generic enough.

833. Find And Replace in String

  • https://expl.ai/APDFXTD

  • String corner cases:

    • Whether there will be overlapping

    • Whether sources/indexes will be sorted

PreviousstackNextintervals

Last updated 3 years ago