Problem:
There is a strange printer with the following two special requirements:
- The printer can only print a sequence of the same character each time.
- 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:
|
1 2 3 |
Input: "aaabbb" Output: 2 Explanation: Print "aaa" first and then print "bbb". |
Example 2:
|
1 2 3 |
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.
Idea:
Dynamic programming
Time Complexity:
O(n^3)
Space Complexity:
O(n^2)
Solution:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Author: Huahua // Time Complexity: O(n^3) // Space Complexity: O(n^2) // Running Time: 22 ms class Solution { public: int strangePrinter(const string& s) { int l = s.length(); t_ = vector<vector<int>>(l, vector<int>(l, 0)); return turn(s, 0, s.length() - 1); } private: // Minimal turns to print s[i] to s[j] int turn(const string& s, int i, int j) { // Empty string if (i > j) return 0; // Solved if (t_[i][j] > 0) return t_[i][j]; // Default behavior, print s[i] to s[j-1] and print s[j] int ans = turn(s, i, j-1) + 1; for (int k = i; k < j; ++k) if (s[k] == s[j]) ans = min(ans, turn(s, i, k) + turn(s, k + 1, j - 1)); return t_[i][j] = ans; } vector<vector<int>> t_; }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua // Time Complexity: O(n^3) // Space Complexity: O(n^2) // Running Time: 31 ms (beat 99.25%) 9/2017 class Solution { public int strangePrinter(String s) { int l = s.length(); t_ = new int[l][l]; return turn(s.toCharArray(), 0, l - 1); } // Minimal turns to print s[i] to s[j] private int turn(char[] s, int i, int j) { // Empty string if (i > j) return 0; // Solved if (t_[i][j] > 0) return t_[i][j]; // Default behavior, print s[i] to s[j-1] and print s[j] int ans = turn(s, i, j-1) + 1; for (int k = i; k < j; ++k) if (s[k] == s[j]) ans = Math.min(ans, turn(s, i, k) + turn(s, k + 1, j - 1)); return t_[i][j] = ans; } private int[][] t_; } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
""" Author: Huahua Time Complexity: O(n^3) Space Complexity: O(n^2) Running Time: 895 ms (beat 66%) 9/2017 """ class Solution(object): def strangePrinter(self, s): """ :type s: str :rtype: int """ l = len(s) self._t = [[0 for _ in xrange(l)] for _ in xrange(l)] return self._turns(s, 0, l - 1) def _turns(self, s, i, j): if i > j: return 0 if self._t[i][j] > 0: return self._t[i][j] ans = self._turns(s, i, j - 1) + 1 for k in xrange(i, j): if s[k] == s[j]: ans = min(ans, self._turns(s, i, k) + self._turns(s, k + 1, j-1)) self._t[i][j] = ans return self._t[i][j] |