มีรายการคำ words และสตริง s หาจำนวนคำใน words ที่เป็น subsequence ของ s
เช่น words=["xz","xw","y"], s="xyz" ให้ 2 เพราะ "xz" และ "y" เป็น subsequence
ขั้นตอนการแก้ปัญหา
- จัดกลุ่มคำตามตัวอักษรแรกใน
d - วนอ่านตัวอักษรใน s:
- นำคำที่ขึ้นต้นด้วยตัวอักษรนั้นออกมาประมวลผล
- ถ้าความยาว 1 เพิ่มคำตอบ
- มิฉะนั้นย้ายส่วนที่เหลือไปกลุ่มตัวอักษรถัดไป
- คืนค่า
ans
ตัวอย่างโค้ด
from collections import defaultdict
class Solution:
def solve(self, words, s):
ans = 0
d = defaultdict(list)
for word in words:
d[word[0]].append(word)
for c in s:
l = d[c]
d[c] = []
for word in l:
if len(word) == 1:
ans += 1
else:
d[word[1]].append(word[1:])
return ans
ob = Solution()
words = ["xz","xw","y"]
s = "xyz"
print(ob.solve(words, s))
อินพุต
["xz","xw","y"], "xyz"
เอาต์พุต
2
