LeetCode 解題筆記：3302. Find the Lexicographically Smallest Valid Sequence

作者：王一哲
日期：2026年8月8日


LeetCode 題目連結：3302. Find the Lexicographically Smallest Valid Sequence

解題想法

中等難度題。題目給兩個字串 $word1$ 及 $word2$，如果最多可以改變 $word1$ 之中的一個字母，如何在 $word1$ 之中找出等於 $word2$ 的子字串，回傳最小字典序子字串於 $word1$ 之中的索引值。這題用貪心法解題比較方便。首先要找出 $word2[j]$ 及之後的字元於 $word1$ 可以被找到且在最右側的位置，將索引值存入陣列 right_match。接下來用貪心法，由 $word1$ 開頭往右找答案 $ans$，如果 $word1[i] = word2[j]$，$i$ 加入 $ans$；如果 $word1[i] \neq word2[j]$ 而且還沒有換過字母，如果已經找到 $word2[m-1]$ 或是 $word2[j+1]$ 及之後的字母可以在 $word1[i]$ 之後被找到，$i$ 加入 $ans$。最後檢查 $ans$ 的長度是否等於 $m$，如果相等回傳 $ans$，反之回傳空陣列。

Python 程式碼

Runtime: 425 ms, beats 84.78%. Memory: 48.21 MB, beats 47.83%.

class Solution:
    def validSequence(self, word1: str, word2: str) -> List[int]:
        n, m = len(word1), len(word2)  # 長度
        # 預處理，找出 word2[j] 及之後的字元於 word1 可以被找到且在最右側的位置
        right_match = [-1] * m
        j = m - 1
        for i in range(n-1, -1, -1):
            if j < 0: break  # 已經找完 word2，中止迴圈
            if word1[i] == word2[j]:
                right_match[j] = i
                j -= 1
        print(right_match)
        # 貪心法，由 word1 開頭往右找答案
        ans = []
        j = 0
        changed = False
        for i in range(n):
            # 已經找完 word2，中止迴圈
            if j == m: break
            # 相同的字母，直接加入 ans
            if word1[i] == word2[j]:
                ans.append(i)
                j += 1
            elif not changed:  # 不同的字母，還沒有換過字母
                # 如果已經找到 word2 最後一個字母或是 word2[j+1] 及之後的字母在 word1[i] 之後能被找到
                if j == m-1 or right_match[j+1] > i:
                    changed = True
                    ans.append(i)
                    j += 1
        # 如果 ans 長度等於 m，回傳 ans，反之回傳 []
        return ans if len(ans) == m else []

C++ 程式碼

Runtime: 34 ms, beats 91.49%. Memory: 109.28 MB, beats 55.32%.

class Solution {
public:
    vector<int> validSequence(string word1, string word2) {
        int n = (int)word1.size(), m = (int)word2.size();  // 長度
        /* 預處理，找出 word2[j] 及之後的字元於 word1 可以被找到且在最右側的位置 */
        vector<int> right_match (m, -1);
        int j = m - 1;
        for(int i = n-1; i >= 0; i--) {
            if (j < 0) break;  // 已經找完 word2，中止迴圈
            if (word1[i] == word2[j]) {
                right_match[j] = i;
                j--;
            }
        }
        /* 貪心法，由 word1 開頭往右找答案 */
        vector<int> ans;
        bool changed = false;
        j = 0;
        for(int i = 0; i < n; i++) {
            // 已經找完 word2，中止迴圈
            if (j == m) break;
            // 相同的字母，直接加入 ans
            if (word1[i] == word2[j]) {
                ans.push_back(i);
                j++;
            } else if (!changed) {  // 不同的字母，還沒有換過字母                
                // 如果已經找到 word2 最後一個字母或是 word2[j+1] 及之後的字母在 word1[i] 之後能被找到
                if (j == m-1 || right_match[j+1] > i) {
                    changed = true;
                    ans.push_back(i);
                    j++;
                }
            }
        }
        // 如果 ans 長度等於 m，回傳 ans，反之回傳 empty
        vector<int> empty;
        return (ans.size() == m ? ans : empty);
    }
};