สมมติว่าเรามีรายการคำและรูปแบบ และเราต้องค้นหาคำในคำที่ตรงกับรูปแบบ ในที่นี้ คำจะจับคู่กับรูปแบบหากมีการเรียงสับเปลี่ยนของตัวอักษร p ดังนั้นหลังจากแทนที่ตัวอักษร x ทุกตัวในรูปแบบด้วย p(x) เราจะได้คำเป้าหมาย เราต้องหารายชื่อคำในคำที่ตรงกับรูปแบบที่กำหนด
ตัวอย่างเช่น หากอินพุตเป็น ["abc","deq","mee","aqq","dkd","ccc"] และรูปแบบเป็น "abb" ผลลัพธ์จะเป็น ["mee" , “aqq”], ที่นี่ mee และ aqq จับคู่สไตล์ของรูปแบบ “abb” แต่ “ccc” ไม่ใช่รูปแบบ เพราะนี่ไม่ใช่การเปลี่ยนแปลง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดหนึ่งวิธี convert() สิ่งนี้จะใช้คำเป็นอินพุต สิ่งนี้จะทำหน้าที่เหมือน −
- ตัวนับ :=1, s :=สตริงว่าง
- s :=s + string เทียบเท่าตัวนับ
- สำหรับฉันอยู่ในช่วง 1 ถึงความยาวของคำ – 1
- j :=i – 1
- ในขณะที่ j>=0
- ถ้า word[j] เป็น word[i] ให้แตก
- ลด j ทีละ 1
- ถ้า j> -1 แล้ว s :=s + s[j] ไม่เช่นนั้นให้เพิ่มตัวนับ 1 และ s :=s + ค่าตัวนับเป็นสตริง
- คืนสินค้า
- วิธีการจริงจะประมาณนี้
- สร้างอาร์เรย์หนึ่ง word_num และนี่ว่างเปล่า สร้างอาร์เรย์ว่างอีกอัน
- สำหรับแต่ละองค์ประกอบ i ในคำ −
- แทรก convert(i) เป็น word_num
- รูปแบบ :=แปลง (รูปแบบ)
- สำหรับฉันอยู่ในช่วง 0 ถึงความยาวของคำ – 1
- ถ้า words_num[i] =รูปแบบ ให้ใส่คำ[i] ลงใน res
- ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object): def findAndReplacePattern(self, words, pattern): words_num = [] result = [] for i in words: words_num.append(self.convert(i)) pattern = self.convert(pattern) for i in range(len(words)): if words_num[i] == pattern: result.append(words[i]) return result def convert(self,word): counter = 1 s = "" s+=str(counter) for i in range(1,len(word)): j= i -1 while j>=0: if word[j] == word[i]: break j-=1 if j >-1: s+=s[j] else: counter+=1 s+=str(counter) return s ob = Solution() print(ob.findAndReplacePattern(["abc","deq","mee","aqq","dkd","ccc"],"abb"))
อินพุต
["abc","deq","mee","aqq","dkd","ccc"] "abb"
ผลลัพธ์
['mee', 'aqq']
