This is the 13th day of my participation in the More text Challenge. For details, see more text Challenge

Weird printer (Question Number 664)

The title

There’s a weird printer that has two special requirements:

  • Printers can only print a sequence of the same characters at a time.
  • New characters can be printed at any start and end at any time and will overwrite existing characters.

Given a string s, your task is to calculate the minimum number of times the printer needs to print it.

Example 1:

Input: s = "aaabbb" Output: 2 Explanation: Print "aaa" first and then "BBB".Copy the code

Example 2:

Input: s = "aba" Output: 2 Explanation: Print "aaa" first and then print "b" in the second position to overwrite the original character 'a'.Copy the code

Tip:

  • 1 <= s.length <= 100
  • sIt consists of lowercase letters

link

Leetcode-cn.com/problems/st…

explain

This one, this one is classical dynamic programming.

The minimum number of printings, which is the optimal solution, obviously requires dynamic programming.

I made a mistake at first, trying to think about all the scenarios, because obviously, if you start with the same letter and end with the same letter, you can reduce the number of times you have to print. If the current letter is the same as the previous letter, you can also reduce the number of times to print.

The author tried to find the combination of letters, and then made different counting methods according to the situation. After trying for three times, he decided to give up, which was obviously an impossible job.

So what do you do? The author did not have a clue after thinking, finally can only look at the answer, the original or DP’s train of thought is wrong.

We should be thinking about the intervals, not the cases.

We can break the string into intervals, such as 🌰 :

'abbbc'
Copy the code

First, divide the chestnuts here into two sections:

'abb', 'bc'
Copy the code

And then open, have been open will become 👇 :

'a', 'b', 'b', 'b', 'c'
Copy the code

Each individual interval is printed once, so you can use this as a baseline to start increasing the interval a little bit.

First look at the ab interval, which obviously needs to be printed twice, then look at the BB interval and print once to find all the two-letter intervals, which should look like this:

'ab': 2
'bb': 1
'bb': 1
'bc': 2
Copy the code

Once you find these intervals, you can expand the intervals to three, four, and the last five letters.

The specific interval method will be explained in detail in the answer, here only to provide ideas.

Your own answer

There is no

Better Way (DP)

As usual, look at the code 👇 :

var strangePrinter = function(s) {
  var len = s.length
      dp = Array.from({length: len}, () => new Array(len).fill(0))
  for (let i = len - 1; i >= 0; i--) {
    dp[i][i] = 1
    for (let j = i + 1; j < len; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = dp[i][j - 1]
      } else {
        var min = Number.MAX_SAFE_INTEGER
        for (let k = i; k < j; k++) {
          min = Math.min(min, dp[i][k] + dp[k+1][j])          
        }
        dp[i][j] = min
      }
    }
  }
  return dp[0][len - 1]
}
Copy the code

So let’s start with the definition of DP, which is a two dimensional array, what does this two dimensional array represent?

DP[I][j] represents the minimum number of times a string can be printed from I to j.

If this interval has only one value, the minimum number of printings between it is 1, that is, DP[I][I] = 1.

After the DP array is initialized, we start the loop.

In order to ensure that the calculation process of dynamic programming satisfies no aftereffect, in the actual code, we need to change the calculation order of dynamic programming and enumerate I from large to small

I can only GET a part of the specific reasons, you can imagine that if it is from the front to the back, then the data behind may be inaccurate, I just have this feeling, the specific reasons are not clear, try to bureau.

So the first layer of the loop, from the back to the front, I goes from large to small. The first thing to do inside the I loop is to assign the initial value:

dp[i][i] = 1
Copy the code

That is, the number of prints is 1 for interval length 1.

And then we start the inner loop, and then we can go back and forth, from I to the end of the array.

If the beginning and end of the interval are the same, that is, s[I] === s[j], then you can directly take the interval value with one less letter, because it can save one time to print. This part is relatively simple.

And then the inner K cycle, which is the last cycle.

The loop of this layer is to splice all the cells in the interval from I to J. It can be seen from the code that the splicing process is actually to take the minimum value, for example, such a cell:

'abcd'
Copy the code

The comparison elements are:

'a', 'bcd'
'ab', 'cd'
'abc', 'd'
'abcd'
Copy the code

Take the minimum value of these combinations as the minimum number of printings in the interval, and so on, you can expand the interval to the whole string interval to get the final result.

So that’s it. It’s actually a little bit more complicated than the perturbation. It’s a little bit harder to think of a three-layer loop.

The time complexity is O(n^3), where n is the length of the string.

The space complexity is O(n^2), where n is the length of the string. We need to save all n^2 states.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ