1312 Minimum Insertion Steps to Make a String Palindrome

1312. Minimum Insertion Steps to Make a String Palindrome This is the daily challenge on 22/Apr/2023. Idea To solve this problem, there is one key point that we can’t miss. Assume x is the length of the longest palindromic subsequence, and n is the length of s, the result is simply n-x This is because for those chars that are not in the longest palindromic subsequence, we have to add one char for each of them to make them palindromic....

April 22, 2023 · mimimi

516 Longest Palindromic Subsequence

516. Longest Palindromic Subsequence Idea I re-visited this problem because of another hard problem (1312), and I found that this problem deserves a post on its own. We’re trying to find the longest palindromic subsequence, there are few ways to solve subsequence problems and probably the first one we should consider is Dynamic Programming(DP). DP State We want the longest, so we start from index 0 and index len-1, and takes them if they are the same, do something else if not, so we need to keep track of two indices, left and right....

April 22, 2023 · mimimi

1639 Number of Ways to Form a Target String Given a Dictionary

In my personal opinion, this stupid problem is harder than an ordinary DP, because: state transition is weird(multiplication…) we need another data structure to pre-compute something Idea We need to match chars in word and chars in target, but with the given restriction. once we take a char in word, the char and the char to the left from all words are not available anymore we can start from any word, not necessarily from the first word target can be shorter than words[0] Base Case Success case: chars in targets are all matched(m>=len(target))....

April 18, 2023 · mimimi

87 Scramble String

87. Scramble String Idea Reading through the description, take note of these: If the length of the string is 1, stop. Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x. The above two pieces of information heavily hint that this is a DP problem. The first sentence tells us the base case, length of string is 1....

April 4, 2023 · mimimi