九章演算法 | Google 面試題：奇怪的印表機

05-03

作者｜陳近南

專欄｜九章演算法

題目描述

一個奇怪的印表機列印時遵守以下兩個特殊的條件：

每次只能列印同一個字元組成的連續序列。
每次列印可以在任何位置開始，在任何位置結束，列印的字元會將原來已有的字元覆蓋。

給定一個只包含小寫字母的字元串，你的任務是計算用該印表機列印出這個字元串所需的最少列印次數。字元串長度不超過100。

樣例

Example 1: 輸入: "aaabbb"輸出: 2說明: 先列印"aaa"，再列印"bbb"。Example 2: 輸入: "aba"輸出: 2說明: 先列印"aaa"，再在中間的位置列印"b"覆蓋之前的」a」。

解題思路

Ⅰ. 一個簡單的想法是，給出的字元串有幾段不同的字元，就列印幾次，不考慮列印覆蓋的情況。比如aabbc，那就列印三次。這是一種貪心策略，但是在某些情況下不能取得最優解，比如aabba，我們先列印aaaaa，然後列印bb，只需要兩次。

Ⅱ. 那麼搜索可行嗎？我們每次搜索起點在最左邊的列印區間（需要搜索終點），我們發現通過記錄目前正確列印到了哪個位置，我們可以直接求的下一次列印的起點。因為我們總需要從第一個出錯的位置開始列印。這樣做是可行的，但是複雜度是指數級別，仍有優化的可能性。

Ⅲ. 結合之前兩種思路，我們來觀察總結一下，列印出來的字元串的特點：

假設某一次印表機列印了若干個a，像這樣：」aaaaaa」，在這之後列印的字元，無非是三種情況：

● 在這段字元串的內部列印，但是不覆蓋這段字元串的一端，例如」abbbaa」、」abbada」。

● 在這段字元串的外部列印，完全不覆蓋這段字元串，例如」bbaaaaaa」、」bbaaaaaaccc」。

● 覆蓋這段字元串的一端，例如」baaaaa」、」baaacccccc」。

上面所說的第三種情況，看起來就像後來的字元都列印在」a」組成的字元串的外部。事實上，如果列印了一串字元串後，再列印一些字元覆蓋這段字元串的端點會造成浪費，也就是說被覆蓋的這字元串的部分一開始完全沒有必要列印，也不會對最終列印次數造成影響。所以，我們可以假定，列印時不存在浪費，也就是說某次列印可以覆蓋前面某一次列印的（不包含端點的）內部，也可以不覆蓋，但是不能覆蓋前面某一次列印的端點。

Ⅳ. 對於一個已知的目標字元串s，我們考慮列印出這個字元串最左邊的字元s[0]的那次列印，我們總可以在列印方案中，把該次列印放到第一次列印。可以這樣做的理由是，由於c中的假定，其它的列印要麼在這次列印的內部（不包含端點），要麼在這次列印的外部，並且由於包含目標字元串的最左端點，所以這次列印也不可能在別的列印的內部。這樣一來我們就可以枚舉包含s[0]的那次列印的長度L，然後把原目標字元串分為s[0 ~ L-1]和s[L ~ N-1]（設原字元串長度為N），其中，由a中的假定可知s[0]==s[L-1]必須成立（因為端點不被覆蓋）。s[0 ~ L-1]的最少列印次數實際等於 s[1 ~ L-1]的最少列印次數（也等於s[0 ~ L-2]的最少列印次數），這是因為列印出其中一個字元串的列印方案可以稍加變動變成另一個的列印方案而不改變列印次數（讀者可以想一想是如何變動的）。s[L ~ N-1]的列印與前面字元的列印沒有關係，可以看成一個新的目標字元串，用同樣的方法分析計算。有兩個特殊情況：L=1時，s[0]==s[L-1]必然成立，這時的答案為1 + s[1 ~ N-1]的最小列印次數；L=N時，應滿足s[0]==s[L-1]==s[N-1]，即左右兩端點相等，答案為s[1 ~ N-1]的最小列印次數。

Ⅴ. 分別計算出s[1 ~ L-1]、s[L ~ N-1]的最小列印次數並相加得到特定L下的列印次數，枚舉所有L，對得到的答案取最小值即可得到最終答案。這樣把一個區間分成兩個小的連續區間求解的方法屬於區間型動態規劃，狀態表示為f[i][j]表示從i到j這段子串最少列印次數。具體可以採用遞推的方式（應先從小到大枚舉區間的長度，因為長區間的答案是由短區間的答案確定的）把所有可能的區間的答案都算出來，也可採用記憶化搜索的遞歸形式實現，邊界條件為：長度為1的區間的字元串最少列印次數為1。枚舉所有區間的時間複雜度為O(n^2)，枚舉分段點的時間複雜度為O(n)，故總的時間複雜度為O(n^3)，額外空間複雜度為O(n^2)。

參考程序

九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧

面試官角度分析

本題的最優解法為區間型動態規劃，難度較大，特別是如何狀態轉移比較難想：以什麼依據將區間分成兩段，分成兩段後如何求解，即使知道寫法，想要說出其中的原委、證明其正確性也不是易事。給出正確的解法可以strong hire。

題目答案鏈接