Leetcode: Similar String Groups

Similar String Groups



Similar Problems:


Two strings X and Y are similar if we can swap two letters (in different positions) of X, so that it equals Y.

For example, “tars” and “rats” are similar (swapping at positions 0 and 2), and “rats” and “arts” are similar, but “star” is not similar to “tars”, “rats”, or “arts”.

Together, these form two connected groups by similarity: {“tars”, “rats”, “arts”} and {“star”}. Notice that “tars” and “arts” are in the same group even though they are not similar. Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group.

We are given a list A of unique strings. Every string in A is an anagram of every other string in A. How many groups are there?

Example 1:

Input: ["tars","rats","arts","star"]
Output: 2

Note:

  1. A.length <= 2000
  2. A[i].length <= 1000
  3. A.length * A[i].length <= 20000
  4. All words in A consist of lowercase letters only.
  5. All words in A have the same length and are anagrams of each other.
  6. The judging time limit has been increased for this question.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/similar-string-groups
// Basic Ideas: BFS + hashmap
//
// Choose the first one to explore
//
// Complexity: Time ?, Space ?
func isSimilar(str1 string, str2 string) bool {
    if len(str1) != len(str2) { return false }
    l := []int{}
    for i:=0; i<len(str1); i++ {
        if str1[i] != str2[i] { l = append(l, i)}
    }
    if len(l) != 2 { return false }
    if str1[l[0]]==str2[l[1]] && str1[l[1]] == str2[l[0]] { return true }
    return false
}

func numSimilarGroups(A []string) int {
    if len(A) == 0 { return 0 }

    res := 0
    unvisited := make(map[int]bool, len(A))
    m := make(map[int]bool, len(A))
    for i:= 0; i<len(A); i++ { unvisited[i] = true }

    for i:= 0; i<len(A); i++ {
        if m[i] == true { continue }
        delete(unvisited, i)
        res++
        queue := []int{}
        queue = append(queue, i)
        // explore this word
        for len(queue) != 0 {
            items := []int{}
            for _, i1 := range queue {
                for i2 := range unvisited {
                    if isSimilar(A[i1], A[i2]) == true {
                        items = append(items, i2)
                        m[i2] = true
                        delete(unvisited, i2)
                    }
                }
            }
            queue = []int{}
            for _, v:= range items { queue = append(queue, v) }
        }
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.