Leetcode Problem 1397. Find All Good Strings

1397. Find All Good Strings

Leetcode Solutions

Memoization DFS & KMP

  1. Preprocess the evil string using the KMP algorithm to create the LPS array.
  2. Define a recursive DFS function that takes the current index, the match length of evil, and boolean flags indicating if the current prefix is still bounded by s1 and s2.
  3. If the match length equals the length of evil, return 0 as the string is not good.
  4. If the current index equals n, return 1 as a valid string is found.
  5. Use memoization to cache results for the current state.
  6. Iterate over all possible characters for the current position, bounded by s1 and s2 if applicable.
  7. For each character, update the match length using the LPS array.
  8. Recursively call the DFS function for the next index with updated parameters.
  9. Sum the results and take modulo 10^9 + 7.
  10. Return the memoized result for the current state.
UML Thumbnail

Digit DP & KMP

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...