1286. Iterator for Combination

Design the CombinationIterator class:

  • CombinationIterator(string characters, int combinationLength) Initializes 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 if and only if there exists a next combination.

 

Example 1:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

 

Constraints:

  • 1 <= combinationLength <= characters.length <= 15
  • All the characters of characters are unique.
  • At most 104 calls will be made to next and hasNext.
  • It's guaranteed that all calls of the function next are valid.

Rust Solution

#[derive(Default)]
struct CombinationIterator {
    combinations: Vec<String>,
    index: usize,
}

impl CombinationIterator {
    fn new(characters: String, combination_length: i32) -> Self {
        let n = combination_length as usize;
        let m = characters.len();
        let mut indexes = vec![];
        let mut combinations = vec![];
        let s: Vec<char> = characters.chars().collect();
        Self::dfs(0, &mut indexes, &mut combinations, &s, n, m);
        let index = 0;
        CombinationIterator {
            combinations,
            index,
        }
    }

    fn dfs(
        start: usize,
        indexes: &mut Vec<usize>,
        combinations: &mut Vec<String>,
        s: &[char],
        n: usize,
        m: usize,
    ) {
        if indexes.len() == n {
            let t: String = indexes.iter().map(|&i| s[i]).collect();
            combinations.push(t);
        } else {
            for i in start..m {
                indexes.push(i);
                Self::dfs(i + 1, indexes, combinations, s, n, m);
                indexes.pop();
            }
        }
    }

    fn next(&mut self) -> String {
        let res = self.combinations[self.index].to_string();
        self.index += 1;
        res
    }

    fn has_next(&self) -> bool {
        self.index < self.combinations.len()
    }
}

#[test]
fn test() {
    let mut iter = CombinationIterator::new("abc".to_string(), 2);
    assert_eq!(iter.has_next(), true);
    assert_eq!(iter.next(), "ab".to_string());
    assert_eq!(iter.has_next(), true);
    assert_eq!(iter.next(), "ac".to_string());
    assert_eq!(iter.has_next(), true);
    assert_eq!(iter.next(), "bc".to_string());
    assert_eq!(iter.has_next(), false);
}

Having problems with this solution? Click here to submit an issue on github.