九章演算法 | Amazon 面試題：Minimum String Array Coverage

來自專欄 九章演算法 - lintcode/leetcode題解

撰文 | JZ

專欄 | 九章演算法

題目描述

給定一個字元串集合tag_list，一個字元串數組all_tags。請尋找最小的all_tags子數組包含tag_list中的所有字元串，輸出這個子數組的長度。如果不存在返回-1。

思路點撥

使用Two pointers，右指針不斷向右移，直到包含所有字元串，使用HashSet維護Two pointers中都有哪些字元串出現，左指針一次移動一下並更新Two pointers中都有哪些字元串出現。時間複雜度O(n)。

考點分析

本題和上題一樣，也是考察的雙指針，不過會多一點小細節要處理，可見amazon是有多喜歡考雙指針，所以熟練掌握雙指針是很有必要的。

九章參考程序

https://www.jiuzhang.com/solution/minimum-string-array-coverage/