diff options
author | Jack Sangdahl <[email protected]> | 2024-09-12 20:50:20 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-12 20:50:20 -0600 |
commit | c7d492eb54368a4280b9e4b001cc6eb07effb51a (patch) | |
tree | 2892ce60a66c384111ec6af014a0e31dd379ba86 | |
parent | 32face77eb9aea8b03b3ce869e2d649e9070df63 (diff) | |
download | leetcode-c7d492eb54368a4280b9e4b001cc6eb07effb51a.tar.gz leetcode-c7d492eb54368a4280b9e4b001cc6eb07effb51a.zip |
1286. iterator for combination
-rw-r--r-- | iterator_for_combination.c | 67 | ||||
-rw-r--r-- | iterator_for_combination.py | 59 |
2 files changed, 126 insertions, 0 deletions
diff --git a/iterator_for_combination.c b/iterator_for_combination.c new file mode 100644 index 0000000..e9b8f71 --- /dev/null +++ b/iterator_for_combination.c @@ -0,0 +1,67 @@ +// 1286. Iterator for Combination +#include "leetcode.h" + +/* + * design the 'CombinationIterator' class: + * - 'CombinationIterator(string characters, int combinationLength)' initialises + * the object with a string 'characters' of sorted distinct lowercase english + * letters and a number 'combinationLength' as arguments + * - 'next()' returns the next combination of length 'combinationLength' in + * lexicographical order + * - 'hasNext()' returns 'true' iff there exists a next combination + */ + +typedef struct c { + char *str; + struct c *next; +} CombinationIterator; + +void get_comb(CombinationIterator **last, char *s, char *tab, int l, int len) { + if (l == len) { + (*last)->next = (CombinationIterator *)malloc(sizeof(CombinationIterator)); + *last = (*last)->next; + (*last)->str = (char *)calloc(len + 1, 1); + while (l--) + ((*last)->str)[l] = tab[l]; + (*last)->next = NULL; + } else if (!*s) + return; + else { + tab[l] = *s; + get_comb(last, s + 1, tab, l + 1, len); + get_comb(last, s + 1, tab, l, len); + } +} + +CombinationIterator *combinationIteratorCreate(char *characters, + int combinationLength) { + CombinationIterator *cmb = + (CombinationIterator *)malloc(sizeof(CombinationIterator)); + cmb->next = NULL; + CombinationIterator *p = cmb; + char tab[combinationLength + 1]; + get_comb(&p, characters, tab, 0, combinationLength); + return cmb; +} + +char *combinationIteratorNext(CombinationIterator *obj) { + char *p = obj->next->str; + obj->next = obj->next->next; + return p; +} + +bool combinationIteratorHasNext(CombinationIterator *obj) { return obj->next; } + +void combinationIteratorFree(CombinationIterator *obj) { free(obj); } + +int main() { + char *characters = "abc"; + CombinationIterator *obj = combinationIteratorCreate(characters, 2); + printf("%s\n", combinationIteratorNext(obj)); // expect: ab + printf("%d\n", combinationIteratorHasNext(obj)); // expect: 1 + printf("%s\n", combinationIteratorNext(obj)); // expect: ac + printf("%d\n", combinationIteratorHasNext(obj)); // expect: 1 + printf("%s\n", combinationIteratorNext(obj)); // expect: bc + printf("%d\n", combinationIteratorHasNext(obj)); // expect: 0 + combinationIteratorFree(obj); +} diff --git a/iterator_for_combination.py b/iterator_for_combination.py new file mode 100644 index 0000000..699bb3d --- /dev/null +++ b/iterator_for_combination.py @@ -0,0 +1,59 @@ +# 1286. Iterator for Combination + +""" +design the 'CombinationIterator' class: +- 'CombinationIterator(string characters, int combinationLength)' initialises +the object with a string 'characters' of sorted distinct lowercase english +letters and a number 'combinationLength' as arguments +- 'next()' returns the next combination of length 'combinationLength' in +lexicographical order +- 'hasNext()' returns 'true' iff there exists a next combination +""" + + +class CombinationIterator(object): + def __init__(self, characters, combinationLength): + """ + :type characters: str + :type combinationLength: int + """ + self.characters = characters + self.n = len(characters) + self.combinations = self.get_comb(self.n, combinationLength) + self.idx = len(self.combinations) - 1 + + def next(self): + """ + :rtype: str + """ + s = "" + for i in range(self.n): + if self.combinations[self.idx][i] != "0": + s += self.characters[i] + self.idx -= 1 + return s + + def hasNext(self): + """ + :rtype: bool + """ + return self.idx > -1 + + def get_comb(self, l, n): + end = int("1" * l, 2) + res = [] + for i in range(end + 1): + b = bin(i)[2:] + if b.count("1") == n: + res.append(b.zfill(l)) + return res + + +if __name__ == "__main__": + obj = CombinationIterator("abc", 2) + print(obj.next()) + print(obj.hasNext()) + print(obj.next()) + print(obj.hasNext()) + print(obj.next()) + print(obj.hasNext()) |