839. Similar String Groups (Hard)

https://leetcode.com/problems/similar-string-groups/

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 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.

Solutions

class Solution {

    // Keep track of visited elements and never work on them twice
    Set<Integer> visited = new HashSet<>();

    public int numSimilarGroups(String[] A) {
        int len = A.length;

        int ans = 0;
        for (int i = 0; i < len; i++) {
            if (visited.contains(i)) {
                continue;
            }

            // Group all the words that similar wth A[i] in A and put them into visited set.
            dfs(A, i);

            ans++;
        }

        return ans;
    }

    private void dfs(String[] A, int id) {
        if (visited.contains(A[id])) {
            return;
        }

        visited.add(id);

        for (int i = 0; i < A.length; i++) {
            if (i == id || visited.contains(i)) {
                continue;
            }

            if (similar(A[id], A[i])) {
                dfs(A, i);
            }
        }
    }

    private boolean similar(String word1, String word2) {
        int diff = 0;

        // bit-to-bit comparision
        for (int i = 0; i < word1.length(); ++i) {
            if (word1.charAt(i) != word2.charAt(i)) {
                diff++;
            }
        }

        return diff <= 2;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""