Another Casual Coder

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/

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

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);
 }
 }
 }
}