Chương trình kiểm tra hai chuỗi khác nhau một ký tự tại cùng vị trí trong Python

Giả sử ta được cung cấp một mảng chứa nhiều chuỗi có cùng độ dài. Ta phải tìm xem có hai chuỗi nào khác nhau đúng một ký tự tại cùng một vị trí hay không. Nếu có sự khác biệt này, trả về True, ngược lại trả về False.

Ví dụ: dict = ['pqrs', 'prqs', 'paqs'], kết quả là True. Các chuỗi trong input đều khác nhau tại chỉ mục 1. Vì vậy, nếu lấy bất kỳ cặp nào, đều có sự khác biệt tại cùng vị trí.

Giải thuật

1. seens := new set
2. Với mỗi word trong dict:
   • Với mỗi chỉ mục i và ký tự c trong word:
     • masked_word := word[:i] + '.' + word[i+1:]
     • Nếu masked_word có trong seens: trả về True
     • Ngược lại: thêm masked_word vào seens
3. Trả về False

Ví dụ (Python)

def solve(dict):
    seens = set()
    for word in dict:
        for i, c in enumerate(word):
            masked_word = word[:i] + '.' + word[i+1:]
            if masked_word in seens:
                return True
            else:
                seens.add(masked_word)
    return False

print(solve(['pqrs', 'prqs', 'paqs']))

Input

['pqrs', 'prqs', 'paqs']

Output

True