[LeetCode] 839. Similar String Groups

scq000 发布于2019-08-16 13:55 / 2697人阅读

Problem

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:

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

Solution

class Solution {
    public int numSimilarGroups(String[] A) {
        if (A == null || A.length == 0) return 0;
        int n = A.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                if (canSwap(A[i], A[j])) {
                    uf.union(i, j);
                }
            }
        }
        return uf.size();
    }
    private boolean canSwap(String a, String b) {
        int count = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i) && count++ == 2) return false;
        }
        return true;
    }
}

class UnionFind {
    int[] parents;
    int[] rank;
    int size;
    public UnionFind(int n) {
        parents = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parents[i] = i;
            rank[i] = 0;
        }
        size = n;
    }
    public int find(int i) {
        if (parents[i] == i) return i;
        int p = find(parents[i]);
        parents[i] = p;
        return p;
    }
    public void union(int a, int b) {
        int pA = find(a);
        int pB = find(b);
        if (pA == pB) return;
        if (rank[pA] > rank[pB]) parents[pB] = pA;
        else if (rank[pB] > rank[pA]) parents[pA] = pB;
        else {
            parents[pA] = pB;
            rank[pB]++;
        }
        size--;
    }
    public int size() {
        return size;
    }
}

混合云云服务器 LeetCode_String Groups Similar LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72571.html

[LeetCode/LintCode] Sentence Similarity

Problem Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar. For example, great acting skills a...

dreamtecher 2019-08-16 12:44 评论0 收藏0
Leetcode PHP题解--D45 872. Leaf-Similar Trees

摘要：题目链接题目分析如果一个二叉树的左节点的后辈节点之和等于右节点的后辈节点，那么称该树为子节点相似树直译的。思路直接遍历左节点和右节点，遍历完判断左右节点之间是否相等即可。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D45 872. Leaf-Similar Trees 题目链接 872. Leaf-Similar Trees 题目分析如果一个二叉树的左节点的后辈节点之和等于右节...

levius 2019-07-01 12:43 评论0 收藏0
leetcode-854-K-Similar Strings

摘要：没有发现字符串的遍历，一种向前，一种向后。递归函数，利用返回结果的话，返回结果是递归到最后，结束遍历以后，得到的结果才有效。题目本质：通过将字符串A的字母之间的连续交换位置，达到两个字符串之间完全相同的情况解析：通过将不相等处的字母，发现之后找到想等的，然后进行位置替换。如此反复。问题在于慢，慢在于只要不相等，就会遍历字符串之后所有的字符，大量重复的无意义的计算比较，所以将...

王笑朝 2019-07-30 17:40 评论0 收藏0
[LeetCode] 482. License Key Formatting

Problem You are given a license key represented as a string S which consists only alphanumeric character and dashes. The string is separated into N+1 groups by N dashes. Given a number K, we would wan...

codercao 2019-08-19 11:18 评论0 收藏0
leetcode-394-Decode String

摘要：原题核心是理解题意，总结规律，属于哪一类题目。完成从内往外层层解决，需要保持字符串的记忆。再加上列表操作和字符串追加的小技巧。应用栈的操作，保持一个字符串的状态，并可以从后往前进行处理。动态规划也可以。正则解法栈队列解法原题： Given an encoded string, return its decoded string. The encoding rule is: k[enc...

snifes 2019-07-30 17:38 评论0 收藏0