Bài toán Khóa & Chìa khóa dùng Hash-map (Lock & Key problem)

Giới thiệu

Một danh sách các khóa khác nhau và một danh sách chìa khóa khác được cho. Nhiệm vụ của ta là tìm sự khớp đúng của khóa và chìa khóa từ danh sách cho trước, và gán chìa khóa đó với khóa khi nó đúng.

Trong cách tiếp cận này, ta sẽ duyệt qua tất cả các khóa và tạo một hash-map, sau đó, mỗi chìa khóa được tìm kiếm trong hash-map. Khi chìa khóa khớp, thì nó được đánh dấu là chìa khóa hợp lệ và gán với một khóa.

Đầu vào và Đầu ra

Đầu vào: Danh sách khóa và chìa khóa.
lock = { ),@,*,^,(,%, !,$,&,#}
key = { !, (, #, %, ), ^, &, *, $, @ }
Đầu ra: Sau khi khớp Khóa và Chìa khóa:
Locks: ! ( # % ) ^ & * $ @
Keys: ! ( # % ) ^ & * $ @

Thuật toán

lockAndKeyProblem(lock, key, n)
Đầu vào: Danh sách khóa, danh sách chìa khóa, n.
Đầu ra: Tìm chìa khóa nào cho khóa nào.

Begin
    định nghĩa hashmap
    for i in range (0 to n-1), do
        hashmap[lock[i]] := i  // thiết lập hashmap cho khóa
    done
    for i in range (0 to n-1), do
        if key[i] được tìm thấy trong hashmap, then
            lock[i] = key[i]
    done
End

Ví dụ (C++)

#include <iostream>
#include <map>
using namespace std;

void show(char array[], int n) {
    for(int i = 0; i < n; i++)
        cout << array[i] << " ";
}

void lockAndKeyProblem(char lock[], char key[], int n) {
    map<char, int> hashMap;
    for(int i = 0; i < n; i++)
        hashMap[lock[i]] = i;  // hash map cho khóa
    for(int i = 0; i < n; i++)  // cho mỗi chìa khóa cho mỗi khóa
        if(hashMap.find(key[i]) != hashMap.end()) {
            lock[i] = key[i];
        }
}

int main() {
    char lock[] = {')','@','*','^','(','%','!','$','&','#'};
    char key[] = {'!','(','#','%','}','^','&','*','$','@'};
    int n = 10;
    lockAndKeyProblem(lock, key, n);
    cout << "After matching Locks and Keys:" << endl;
    cout << "Locks: "; show(lock, n); cout << endl;
    cout << "Keys: "; show(key, n); cout << endl;
}

Kết quả

After matching Locks and Keys:
Locks: ! ( # % ) ^ & * $ @
Keys: ! ( # % ) ^ & * $ @