Space is cheap. Time, isn't

 As the say goes: "Space is cheap. Time, isn't". In today's world it is almost always the case that you can spare an extra few bytes here and there, but rest assure that your customer won't spare few extra milliseconds to wait for your site to load. Always err on the side of optimizing for speed. Mem is cheap.

Here is the problem (LC, medium): https://leetcode.com/problems/iterator-for-combination/

1286. Iterator for Combination

Medium

Design an Iterator class, which has:

• A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
• A function next() that returns the next combination of length combinationLength in lexicographical order.
• A function hasNext() that returns True if and only if there exists a next combination.

 

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

 

Constraints:

• 1 <= combinationLength <= characters.length <= 15
• There will be at most 10^4 function calls per test.
• It's guaranteed that all calls of the function next are valid.

Accepted

34,690

Submissions

48,996

Well, it does not hurt to take a quick peek at hint #1: "Generate all combinations as a preprocessing.". I think that says it all. To generate all the combinations, do that in the constructor itself (simple recursion with backtracking and search space pruning), cache it (I used a list, but feel free to use your favorite dynamic-mem allocation data structure) and then the Next and HasNext functions become extremely simple. Code is down below, cheers, ACC.

public class CombinationIterator
{
    private List list = null;
    private int index = 0;
    public CombinationIterator(string characters, int combinationLength)
    {
        list = new List();
        CreateList(characters, 0, "", combinationLength);
        index = 0;
    }

    public string Next()
    {
        string retVal = list[index];
        index++;
        return retVal;
    }

    public bool HasNext()
    {
        return list != null && index < list.Count;
    }

    private void CreateList(string characters, int index, string current, int len)
    {
        if (current.Length == len)
        {
            list.Add(current);
            return;
        }

        for (int i = index; i < characters.Length; i++)
        {
            if (current.Length < len)
            {
                CreateList(characters, i + 1, current + characters[i], len);
            }
        }
    }
}