題目描述:給定一個字串 word 和一個縮寫 abbr,判斷 abbr 是否為 word 的合法縮寫。縮寫規則:數字代表跳過對應數量的字元;數字不可有前導零(如 01 不合法);字母必須與 word 對應位置完全相同。
解題思路:使用兩個指標分別掃描 word(指標 i)和 abbr(指標 j)。遇到字母時,直接比對 word[i] 與 abbr[j],若不同則回傳 false,相同則兩指標各前進一步。遇到數字時,先檢查是否為 '0'(前導零,直接回傳 false),再解析完整的數字(可能是多位數),將解析出的數值加到 i,跳過對應的 word 字元。掃描結束後,若 i == word.size() 且 j == abbr.size(),代表雙方都剛好用完,回傳 true,否則回傳 false。
時間複雜度:O(max(|word|, |abbr|)) — 兩個指標各自最多掃描一遍各自的字串,每個字元只被訪問一次。
空間複雜度:O(1) — 只使用固定數量的指標與整數變數,無額外資料結構。
1. Initialize pointer i = 0 (for word), j = 0 (for abbr)
2. While i < len(word) and j < len(abbr):
a. If abbr[j] is a digit:
- If abbr[j] == '0', return false (leading zero)
- Parse the full number: collect consecutive digits into num
- Advance i by num (skip characters in word)
b. Else (abbr[j] is a letter):
- If word[i] != abbr[j], return false
- Increment both i and j
3. Return true if and only if i == len(word) and j == len(abbr)方法一:正則表達式比對
將 abbr 轉換為正規表達式(例如把數字 3 替換為 .{3}),再用 regex_match 比對 word。實作較直覺,但正則引擎有額外開銷,時間複雜度取決於正則實作,一般為 O(|word| * |abbr|),空間複雜度 O(|abbr|),不適合競賽場景。
方法二:遞迴解析
以遞迴方式處理:若 abbr 開頭是字母,比對後遞迴處理剩餘部分;若是數字,解析數字後跳過 word 相應長度再遞迴。邏輯清晰但有遞迴呼叫棧開銷,時間複雜度 O(|abbr|),空間複雜度 O(|abbr|)(遞迴深度)。
01 合法,代表跳過 1 個字元),你需要修改哪個判斷條件?"i18n" 可代表 "internationalization")?