資訊專欄INFORMATION COLUMN
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.
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72571.html
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...
摘要：題目鏈接題目分析如果一個二叉樹的左節(jié)點(diǎn)的后輩節(jié)點(diǎn)之和等于右節(jié)點(diǎn)的后輩節(jié)點(diǎn)，那么稱該樹為子節(jié)點(diǎn)相似樹直譯的。思路直接遍歷左節(jié)點(diǎn)和右節(jié)點(diǎn)，遍歷完判斷左右節(jié)點(diǎn)之間是否相等即可。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 D45 872. Leaf-Similar Trees 題目鏈接 872. Leaf-Similar Trees 題目分析 如果一個二叉樹的左節(jié)點(diǎn)的后輩節(jié)點(diǎn)之和等于右節(jié)...
摘要：沒有發(fā)現(xiàn)字符串的遍歷，一種向前，一種向后。遞歸函數(shù)，利用返回結(jié)果的話，返回結(jié)果是遞歸到最后，結(jié)束遍歷以后，得到的結(jié)果才有效。 題目本質(zhì)：通過將字符串A的字母之間的連續(xù)交換位置，達(dá)到 兩個字符串之間完全相同的情況解析：通過將不相等處的字母，發(fā)現(xiàn)之后找到想等的，然后進(jìn)行位置替換。如此反復(fù)。 問題在于慢，慢在于只要不相等，就會遍歷字符串之后所有的字符，大量重復(fù)的無意義的計(jì)算比較，所以將...
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...
摘要：原題核心是理解題意，總結(jié)規(guī)律，屬于哪一類題目。完成從內(nèi)往外層層解決，需要保持字符串的記憶。再加上列表操作和字符串追加的小技巧。應(yīng)用棧的操作，保持一個字符串的狀態(tài)，并可以從后往前進(jìn)行處理。動態(tài)規(guī)劃也可以。正則解法棧隊(duì)列解法 原題： Given an encoded string, return its decoded string. The encoding rule is: k[enc...
閱讀 2379·2021-11-11 16:54
閱讀 2631·2021-09-26 09:47
閱讀 3992·2021-09-08 09:36
閱讀 2742·2021-07-25 21:37
閱讀 934·2019-08-30 15:54
閱讀 2547·2019-08-30 14:22
閱讀 3256·2019-08-30 13:57
閱讀 2607·2019-08-29 17:17
