[LeetCode] 839. Similar String Groups

scq000 發布于2019-08-16 13:55 / 2821人閱讀

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;
    }
}

云服務器 GPU云服務器 LeetCode_String Groups Similar LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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