題目資訊

題目編號: 1055
題目連結: Shortest Way to Form String
主題: Two Pointers, String, Binary Search, Greedy

題目敘述

字串的子序列是一個新字串，它是從原始字串中刪除一些（可以為零個）字符而形成的，並且不打亂剩餘字符的相對位置。（例如，「ace」是「abcde」的子序列，而「aec」不是）。

給定兩個字串 source 和 target，返回 source 的子序列，使其連接等於 target 的最小數量。如果任務不可能完成，則返回 -1。

範例 1:

輸入: source = “abc”, target = “abcbc”
輸出: 2
解釋: 目標字串 “abcbc” 可以由 “abc” 和 “bc” 組成，這兩者都是來源字串 “abc” 的子序列。

範例 2:

輸入: source = “abc”, target = “acdbc”
輸出: -1
解釋: 由於目標字串中的字符 “d”，無法從來源字串的子序列構建目標字串。

範例 3:

輸入: source = “xyz”, target = “xzyxz”
輸出: 3
解釋: 目標字串可以如下構建 “xz” + “y” + “xz”。

限制條件:

$1 \leq \text{source.length}, \text{target.length} \leq 1000$
source 和 target 由小寫英文字母組成。

直覺

這個問題涉及到通過連接source字串的子序列來形成target字串。子序列可以通過刪除字符來形成，但必須保留剩餘字符的順序。問題的核心在於確定所需的最少子序列數量。如果target中的任何字符不在source中，那麼就無法形成target字串，應返回 -1。否則，解決方案是在兩個字串中導航，並計算需要多少次完整或部分遍歷source才能匹配target。

解法

該解法運用了一種貪心和雙指針的方法，以高效地解決此問題。

集合初始化: 首先，將source字串中的每個唯一字符存入一個集合中。這樣可以快速判斷target中的某個字符是否不存在於source。
立即不可能性檢查: 在繼續之前，檢查target中的每個字符是否都存在於source中。如果集合中不包含某個target中的字符，返回-1，因為任何source的子序列都不可能形成該字符。
雙指針技術: 使用兩個指針：sourceIdx遍歷source，targetIdx遍歷target。
- 開始時將subsequencesCount初始化為1，表示至少需要一個子序列。
- 重複執行，直到targetIdx達到target的長度。
遍歷邏輯:
- 增加sourceIdx來遍歷source字串。
- 如果sourceIdx超過了source的長度，增加subsequencesCount，表示需要一個新的子序列，並將sourceIdx重設為0。
匹配字符: 在主循環中使用另一個循環來找到source中與target中當前字符匹配的下一個字符。如果找到匹配項，前進targetIdx。
子序列計數: 繼續遍歷source，並在需要時重設，直到所有target的字符都能被形成。在這次遍歷結束時，subsequencesCount的值會表示形成target所需的最小source子序列數量。

整體而言，這個方法高效地結合了掃描和匹配任務，由兩個指針控制，並在source遍歷耗盡時進行完整重設，從而保證了最佳的子序列枚舉。

程式碼

C++

class Solution {
public:
    int shortestWay(string source, string target) {
        // 建立一個集合來保存來自 `source` 字串的唯一字元。
        set<char> sourceSet;

        // 將 `source` 中的每個字元插入集合中以便快速查詢。
        for (char c : source) {
            sourceSet.insert(c);
        }

        // 檢查 `target` 中的每個字元是否存在於 `source` 中。如果不存在，返回 -1。
        for (char c : target) {
            if (sourceSet.count(c) == 0) {
                return -1;
            }
        }

        // 初始化所需的子序列數。
        int subsequencesCount = 1;
        int sourceIdx = -1;  // `source` 字串中的索引。
        int targetIdx = 0;   // `target` 字串中的索引。

        // 遍歷 `target` 字串。
        while (targetIdx < target.size()) {
            sourceIdx++;
            
            // 如果 `sourceIdx` 超過了 `source` 的長度，我們需要增加一個子序列。
            if (sourceIdx == source.size()) {
                subsequencesCount++;
                sourceIdx = 0;
            }

            // 在 `source` 中移動，直到找到匹配 `target[targetIdx]` 的字元。
            while (source[sourceIdx] != target[targetIdx]) {
                sourceIdx++;
                if (sourceIdx == source.size()) {
                    subsequencesCount++;
                    sourceIdx = 0;
                }
            }
            
            // 移動到 `target` 中的下一個字元。
            targetIdx++;
        }

        // 返回所需的總子序列數。
        return subsequencesCount;
    }
};

Python

class Solution:
    def shortestWay(self, source: str, target: str) -> int:
        # 創建一個集合來保存`source`字符串中的唯一字符。
        sourceSet = set()

        # 將`source`中的每個字符插入到集合中，以便快速查找。
        for c in source:
            sourceSet.add(c)

        # 檢查`target`中的每個字符是否存在於`source`中。如果不存在，返回-1。
        for c in target:
            if c not in sourceSet:
                return -1

        # 初始化所需的子序列數量。
        subsequencesCount = 1
        sourceIdx = -1  # `source`字符串中的索引。
        targetIdx = 0   # `target`字符串中的索引。

        # 遍歷`target`字符串。
        while targetIdx < len(target):
            sourceIdx += 1
            
            # 如果`sourceIdx`超過了`source`的長度，我們需要額外的子序列。
            if sourceIdx == len(source):
                subsequencesCount += 1
                sourceIdx = 0

            # 遍歷`source`，直到我們找到匹配`target[targetIdx]`的字符。
            while source[sourceIdx] != target[targetIdx]:
                sourceIdx += 1
                if sourceIdx == len(source):
                    subsequencesCount += 1
                    sourceIdx = 0
            
            # 移動到`target`中的下一個字符。
            targetIdx += 1

        # 返回所需的子序列總數。
        return subsequencesCount

複雜度分析

時間複雜度: $O(n \times m)$，其中 $n$ 是 source 字串的長度，$m$ 是 target 字串的長度。這是因為對於 target 中的每個字元，演算法可能需要遍歷整個 source 字串以找到匹配的字元。
空間複雜度: $O(n)$，其中 $n$ 是 source 字串的長度。這是由於用於儲存來自 source 字串的唯一字元之集合 sourceSet 所耗費的空間。集合最多可以包含 source 的所有字元。

CS Note
En

Leetcode 1055. Shortest Way to Form String

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析