Skip to content

Commit 0a00e64

Browse files
fishercoder1534fishercoder1534
committed
add 1286
1 parent 2ff17c0 commit 0a00e64

File tree

3 files changed

+116
-0
lines changed

3 files changed

+116
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,7 @@ _If you like this project, please leave me a star._ ★
4444
|1295|[Find Numbers with Even Number of Digits](https://leetcode.com/problems/find-numbers-with-even-number-of-digits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1295.java) | [:tv:](https://youtu.be/HRp8mNJvLZ0) |Easy||
4545
|1290|[Convert Binary Number in a Linked List to Integer](https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1290.java) | |Easy||
4646
|1287|[Element Appearing More Than 25% In Sorted Array](https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1287.java) | [:tv:](https://youtu.be/G74W8v2yVjY) |Easy||
47+
|1286|[Iterator for Combination](https://leetcode.com/problems/iterator-for-combination/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1286.java) | |Medium|Backtracking, Design|
4748
|1282|[Group the People Given the Group Size They Belong To](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1282.java) | [:tv:](https://www.youtube.com/watch?v=wGgcRCpSAa8)|Medium||
4849
|1281|[Subtract the Product and Sum of Digits of an Integer](https://leetcode.com/problems/subtract-the-product-and-sum-of-digits-of-an-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1281.java) | |Easy||
4950
|1277|[Count Square Submatrices with All Ones](https://leetcode.com/problems/count-square-submatrices-with-all-ones/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1277.java) | |Medium||

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

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* 1286. Iterator for Combination
8+
*
9+
* Design an Iterator class, which has:
10+
* A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
11+
* A function next() that returns the next combination of length combinationLength in lexicographical order.
12+
* A function hasNext() that returns True if and only if there exists a next combination.
13+
*
14+
* Example:
15+
* CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.
16+
* iterator.next(); // returns "ab"
17+
* iterator.hasNext(); // returns true
18+
* iterator.next(); // returns "ac"
19+
* iterator.hasNext(); // returns true
20+
* iterator.next(); // returns "bc"
21+
* iterator.hasNext(); // returns false
22+
*
23+
* Constraints:
24+
* 1 <= combinationLength <= characters.length <= 15
25+
* There will be at most 10^4 function calls per test.
26+
* It's guaranteed that all calls of the function next are valid.
27+
* */
28+
public class _1286 {
29+
public static class Solution1 {
30+
public static class CombinationIterator {
31+
32+
List<String> list;
33+
int index;
34+
int combinationLength;
35+
boolean[] visited;
36+
37+
public CombinationIterator(String characters, int combinationLength) {
38+
this.index = 0;
39+
this.list = new ArrayList<>();
40+
this.combinationLength = combinationLength;
41+
this.visited = new boolean[characters.length()];
42+
buildAllCombinations(characters, 0, new StringBuilder(), visited);
43+
}
44+
45+
private void buildAllCombinations(String characters, int start, StringBuilder sb, boolean[] visited) {
46+
if (sb.length() == combinationLength) {
47+
list.add(sb.toString());
48+
return;
49+
} else {
50+
for (int i = start; i < characters.length(); ) {
51+
if (!visited[i]) {
52+
sb.append(characters.charAt(i));
53+
visited[i] = true;
54+
buildAllCombinations(characters, i++, sb, visited);
55+
visited[i - 1] = false;
56+
sb.setLength(sb.length() - 1);
57+
} else {
58+
i++;
59+
}
60+
}
61+
}
62+
}
63+
64+
public String next() {
65+
return list.get(index++);
66+
}
67+
68+
public boolean hasNext() {
69+
return index < list.size();
70+
}
71+
}
72+
}
73+
}

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

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._1286;
4+
import org.junit.Test;
5+
6+
import static org.junit.Assert.assertEquals;
7+
8+
public class _1286Test {
9+
private static _1286.Solution1.CombinationIterator combinationIterator;
10+
11+
@Test
12+
public void test1() {
13+
combinationIterator = new _1286.Solution1.CombinationIterator("abc", 2);
14+
assertEquals("ab", combinationIterator.next());
15+
assertEquals(true, combinationIterator.hasNext());
16+
assertEquals("ac", combinationIterator.next());
17+
assertEquals(true, combinationIterator.hasNext());
18+
assertEquals("bc", combinationIterator.next());
19+
assertEquals(false, combinationIterator.hasNext());
20+
}
21+
22+
@Test
23+
public void test2() {
24+
combinationIterator = new _1286.Solution1.CombinationIterator("abc", 3);
25+
assertEquals("abc", combinationIterator.next());
26+
assertEquals(false, combinationIterator.hasNext());
27+
}
28+
29+
@Test
30+
public void test3() {
31+
combinationIterator = new _1286.Solution1.CombinationIterator("abcd", 3);
32+
assertEquals("abc", combinationIterator.next());
33+
assertEquals(true, combinationIterator.hasNext());
34+
assertEquals("abd", combinationIterator.next());
35+
assertEquals(true, combinationIterator.hasNext());
36+
assertEquals("acd", combinationIterator.next());
37+
assertEquals(true, combinationIterator.hasNext());
38+
assertEquals("bcd", combinationIterator.next());
39+
assertEquals(false, combinationIterator.hasNext());
40+
}
41+
42+
}

0 commit comments

Comments
 (0)