Hai chuỗi str1 và str2 là tương tự nếu chúng ta có thể hoán đổi hai chữ cái (ở vị trí khác nhau) của str1, sao cho nó bằng str2. Ngoài ra, hai chuỗi str1 và str2 là tương tự nếu chúng bằng nhau.
Ví dụ, "tars" và "rats" là tương tự (hoán đổi vị trí 0 và 2), và "rats" và "arts" là tương tự, nhưng "star" không tương tự "tars", "rats", hay "arts".
Cùng nhau, chúng hình thành hai nhóm kết nối bởi tính tương tự: {"tars", "rats", "arts"} và {"star"}. Chú ý "tars" và "arts" ở cùng nhóm dù không trực tiếp tương tự.
Định nghĩa chính thức, mỗi nhóm sao cho một từ nằm trong nhóm nếu và chỉ nếu nó tương tự với ít nhất một từ khác trong nhóm.
Cho một danh sách arr các chuỗi nơi mọi chuỗi trong arr là anagram của mọi chuỗi khác trong arr. Chúng ta cần viết một hàm tìm ra có bao nhiêu nhóm.
Ví dụ
Dưới đây là mã nguồn:
const arr = ["tars","rats","arts","star"]; const isSimilar = (str1, str2) => { const obj = {} let counter = 0 for(let i=0; i< str1.length; i++){ if(str1[i] !== str2[i]) { counter++ } obj[str1[i]] = str2[i] } return counter === 2? true : false } const similarStringGroup = (arr = []) => { const group = [[arr[0]]] for(let i=1; i<arr.length; i++){ let match = false for(let j=0; j<group.length; j++){ for(let k=0; k< group[j].length; k++){ const booleanMatch = isSimilar(group[j][k], arr[i]) if(booleanMatch) { group[j].push(arr[i]); match = true break; } } if(match === true) { break } } if(match === false){ group.push([arr[i]]) } } return group.length } console.log(similarStringGroup(arr));Kết quả
Đầu ra trên console:
2
Giải thích: Similar String Groups (LeetCode 839). Xây đồ thị: node = string, edge = similar (khác nhau đúng 2 vị trí). Tìm số connected components. Code dùng Union-Find ngầm (group array). isSimilar check diff count == 2 (vì anagram đảm bảo cùng multiset chars). O(n² * L) time.