664. Strange Printer

LeetCode 664. Strange Printer

Description

There is a strange printer with the following two special requirements:

1. The printer can only print a sequence of the same character each time.

2. At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Example 1:

Input: "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".

Example 2:

Input: "aba"
Output: 2
Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.

Hint : Length of the given string will not exceed 100.

Tags

Dynamic Programming, Depth-first Search

Solution

• State: f[i][j] represents the minimum operations to print s[i:j] ;

• Transform:

  • s[i]=s[j]: We only need to consider the minimum operations to print s[i:j-1], because we can print s[i] and s[j] in one single operation;

  • s[i]≠s[j]: We have to split s[i:j] into 2 parts and find the minimum operations required by both parts.

• Edge cases: f[i][i]=1, which means we only need to print once for a single character;

• Answer: f[0][n - 1].

Note that we iterate i from right to left and j from left to right, to ensure we have obtained f[i][k] and f[k+1][j] when we need to compute f[i][j].

Complexity

• Time complexity: $O(n^3)$

• Space complexity: $O(n^2)$

Code

func strangePrinter(s string) int {
	dp := make([][]int, len(s))
	for i := range dp {
		dp[i] = make([]int, len(s))
	}
	for i := len(s) - 1; i >= 0; i-- {
		dp[i][i] = 1
		for j := i + 1; j < len(s); j++ {
			if s[i] == s[j] {
				dp[i][j] = dp[i][j-1]
			} else {
				dp[i][j] = 1 << 31
				for k := i; k < j; k++ {
					dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])
				}
			}
		}
	}
	return dp[0][len(s)-1]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

Reference

1. 奇怪的打印机