Chuỗi tương đương nhỏ nhất theo từ điển (Lexicographically Smallest Equivalent String) trong C++

Giả sử ta có chuỗi A và B cùng độ dài, ta có thể nói A[i] và B[i] là các ký tự tương đương. Ví dụ, nếu A = "abc" và B = "cde", thì 'a' = 'c', 'b' = 'd' và 'c' = 'e'. Các ký tự tương đương tuân theo quy tắc quan hệ tương đương:

• Tính phản xạ: 'a' = 'a'.

• Tính đối xứng: 'a' = 'b' ngụ ý 'b' = 'a'.

• Tính bắc cầu: 'a' = 'b' và 'b' = 'c' ngụ ý 'a' = 'c'.

Ví dụ, cho thông tin tương đương từ A và B, S = "eed", "acd", và "aab" là các chuỗi tương đương, và "aab" là chuỗi tương đương nhỏ nhất theo từ điển của S. Ta phải tìm chuỗi tương đương nhỏ nhất theo từ điển của S bằng thông tin từ A và B.

Ví dụ: A = "parker", B = "morris", S = "parser", kết quả "makkek". Dựa trên thông tin tương đương, nhóm ký tự: [m,p], [a,o], [k,r,s], [e,i]. Ký tự trong mỗi nhóm tương đương và sắp xếp theo thứ tự từ điển. Kết quả "makkek".

Để giải quyết, ta thực hiện các bước sau:

• Tạo mảng parent.

• Định nghĩa phương thức getParent(), nhận ký tự x.

• Nếu parent[x - ASCII 'a'] bằng -1, trả về x - ASCII 'a'.

• parent[x - ASCII 'a'] := getParent(ASCII 'a' + parent[x - ASCII 'a']).

• Trả về parent[x - ASCII 'a'].

• Định nghĩa phương thức union(), nhận a và b.

• parentA := getParent(a), parentB := getParent(b).

• Nếu parentA = parentB, trả về. Ngược lại nếu parentA < parentB, parent[parentB] := parentA, ngược lại parent[parentA] := parentB.

• Từ phương thức main:

• Đặt parent := mảng kích thước 26 điền -1.

• Với i từ 0 đến 25: union(A[i], B[i]).

• Tạo chuỗi rỗng ret.

• Với i từ 0 đến kích thước S: ret := ret + getParent(S[i]) + 'a'.

• Trả về ret.

Xem triển khai dưới đây để hiểu rõ hơn:

Ví dụ minh họa

#include <bits/stdc++.h> using namespace std; class Solution {    public:    vector <int> parent;    int getParent(char x){       if(parent[x - 'a'] == -1) return x - 'a';       return parent[x - 'a'] = getParent('a' + parent[x - 'a']);    }    void unionn(char a, char b){       int parentA = getParent(a);       int parentB = getParent(b);       if(parentA == parentB) return;       if(parentA < parentB){          parent[parentB] = parentA;       }else{          parent[parentA] = parentB;       }    }    string smallestEquivalentString(string A, string B, string S) {       parent = vector <int>(26, -1);       for(int i = 0; i < A.size(); i++){          unionn(A[i], B[i]);       }       string ret = "";       for(int i = 0; i < S.size(); i++){          ret += getParent(S[i]) + 'a';       }       return ret;    } }; main(){    Solution ob;    cout << (ob.smallestEquivalentString("parker","morris","parser")); }

Đầu vào

"parker" "morris" "parser"

Kết quả

makkek