Skip to content

Commit 9d4efd0

Browse files
fishercoder1534fishercoder1534
committed
add 893
1 parent 383da8a commit 9d4efd0

File tree

3 files changed

+98
-0
lines changed

3 files changed

+98
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,7 @@ _If you like this project, please leave me a star._ ★
109109
|897|[Increasing Order Search Tree](https://leetcode.com/problems/increasing-order-search-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_897.java) | O(n) | O(n) | |Easy| DFS, recursion
110110
|896|[Monotonic Array](https://leetcode.com/problems/monotonic-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_896.java) | O(n) | O(1) | |Easy|
111111
|890|[Find and Replace Pattern](https://leetcode.com/problems/find-and-replace-pattern/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_890.java) | O(n) | O(1) | |Medium|
112+
|893|[Groups of Special-Equivalent Strings](https://leetcode.com/problems/groups-of-special-equivalent-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_893.java) | | | |Easy|
112113
|888|[Fair Candy Swap](https://leetcode.com/problems/fair-candy-swap/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_888.java) | O(n) | O(1) | |Easy|
113114
|885|[Spiral Matrix III](https://leetcode.com/problems/spiral-matrix-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_885.java) | | | |Medium|
114115
|884|[Uncommon Words from Two Sentences](https://leetcode.com/problems/uncommon-words-from-two-sentences/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_884.java) | O(n) | O(k) | |Easy|

‎src/main/java/com/fishercoder/solutions/_893.java

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.Arrays;
4+
import java.util.HashMap;
5+
import java.util.HashSet;
6+
import java.util.Map;
7+
import java.util.Set;
8+
import java.util.stream.Collectors;
9+
10+
/**
11+
* 893. Groups of Special-Equivalent Strings
12+
*
13+
* You are given an array A of strings.
14+
* A move onto S consists of swapping any two even indexed characters of S, or any two odd indexed characters of S.
15+
* Two strings S and T are special-equivalent if after any number of moves onto S, S == T.
16+
* For example, S = "zzxy" and T = "xyzz" are special-equivalent because we may make the moves "zzxy" -> "xzzy" -> "xyzz"
17+
* that swap S[0] and S[2], then S[1] and S[3].
18+
*
19+
* Now, a group of special-equivalent strings from A is a non-empty subset of A such that:
20+
* Every pair of strings in the group are special equivalent, and;
21+
* The group is the largest size possible (ie., there isn't a string S not in the group such that S is special equivalent to every string in the group)
22+
* Return the number of groups of special-equivalent strings from A.
23+
*
24+
* Example 1:
25+
* Input: ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
26+
* Output: 3
27+
* Explanation:
28+
* One group is ["abcd", "cdab", "cbad"], since they are all pairwise special equivalent, and none of the other strings are all pairwise special equivalent to these.
29+
* The other two groups are ["xyzz", "zzxy"] and ["zzyx"]. Note that in particular, "zzxy" is not special equivalent to "zzyx".
30+
*
31+
* Example 2:
32+
* Input: ["abc","acb","bac","bca","cab","cba"]
33+
* Output: 3
34+
*
35+
* Note:
36+
* 1 <= A.length <= 1000
37+
* 1 <= A[i].length <= 20
38+
* All A[i] have the same length.
39+
* All A[i] consist of only lowercase letters.
40+
* */
41+
public class _893 {
42+
public static class Solution1 {
43+
/**my original solution, a bit length:
44+
* generate a unique signaure as key for each equivelant group and sum them up*/
45+
public int numSpecialEquivGroups(String[] A) {
46+
return Arrays.stream(A).map(this::getCommonKey).collect(Collectors.toSet()).size();
47+
}
48+
49+
private String getCommonKey(String word) {
50+
char[] oddIndexed = new char[word.length() / 2];
51+
char[] evenIndexed = new char[word.length() / 2 + (word.length() % 2 == 0 ? 0 : 1)];
52+
char[] array = word.toCharArray();
53+
for (int i = 0; i < array.length - 1; i += 2) {
54+
evenIndexed[i / 2] = array[i];
55+
oddIndexed[i / 2] = array[i + 1];
56+
}
57+
if (word.length() % 2 != 0) {
58+
evenIndexed[evenIndexed.length - 1] = array[array.length - 1];
59+
}
60+
Arrays.sort(oddIndexed);
61+
Arrays.sort(evenIndexed);
62+
return new StringBuffer().append(new String(evenIndexed)).append(new String(oddIndexed)).toString();
63+
}
64+
}
65+
}

‎src/test/java/com/fishercoder/_893Test.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._893;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
public class _893Test {
10+
private static _893.Solution1 solution1;
11+
12+
@BeforeClass
13+
public static void setup() {
14+
solution1 = new _893.Solution1();
15+
}
16+
17+
@Test
18+
public void test1() {
19+
assertEquals(3, solution1.numSpecialEquivGroups(new String[]{"abcd", "cdab", "cbad", "xyzz", "zzxy", "zzyx"}));
20+
}
21+
22+
@Test
23+
public void test2() {
24+
assertEquals(3, solution1.numSpecialEquivGroups(new String[]{"abc", "acb", "bac", "bca", "cab", "cba"}));
25+
}
26+
27+
@Test
28+
public void test3() {
29+
assertEquals(1, solution1.numSpecialEquivGroups(new String[]{"abcd", "cdab", "adcb", "cbad"}));
30+
}
31+
32+
}

0 commit comments

Comments
 (0)