[leetcode #1286] Iterator for Combination

Problem

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 10⁴ calls will be made to next and hasNext.
・ It's guaranteed that all calls of the function next are valid.

Idea

알파벳이 정렬된 순서로 단 한 번만 등장하는 string과 이 알파벳을 조합하는 길이가 input으로 들어오는 클래스인 CombinationIterator를 디자인하는 문제다.

클래스가 제공하는 기능은 combination된 string을 리턴하는 next() 함수와 다음 combination이 존재하는지 확인하는 hasNext() 함수다.

index를 잘 옮겨서 combination된 string을 하나씩 리턴하면 되는 문제지만, 말처럼 쉬운 문제는 아니다. while문을 쓰다보면 Time Limit Exceeded에 걸리지는 않을까 의심이 되기 때문에 코드로 옮기기가 망설여진다. 이럴 때면 항상 먼저 코드를 짜고 Time Limit Exceeded에 걸리는 지 확인을 먼저 하면 된다. 실행에 먼저 옮기는 것이 그 무엇보다 중요하다.

생성자에서는 string을 바꿔줄 StringBuilder를 만들고, input과 combinationLength를 저장한다. 그리고 hashMap을 통해 각 알파벳이 저장된 index를 확인하도록 한다. 처음에 combinationLength를 만족할 때까지 sb를 채우고, 모든 알파벳의 index를 hashMap에 저장한다.

next() 함수를 디자인하는 것이 어렵다. 우선 string builder에 저장되어 있는 값을 res로 바꾼다. 그리고 다음에 리턴할 string이 무엇인지 미리 저장해야 한다.

1. StringBuilder의 끝부분이 input의 끝부분과 같다면 해당 부분을 전부 삭제해야 한다. 이는 next()로 리턴할 string의 앞쪽 알파벳이 바뀌어야 하기 때문이다.

2. 만약 StringBuilder의 string이 input의 끝부분에 도달했다면 더 이상 처리하지 않는다. 이 때 StringBuilder의 길이가 0이 되므로 hasNext()는 false를 리턴하게 된다.

3. StringBuilder에 남아있는 마지막 character를 hashmap의 다음 character로 바꾸어준다.

4. StringBuilder에 채울 나머지 문자는 3단계에서 채운 문자 이후의 문자들로 지정하면 된다.

실제로 간단해 보이는 알고리즘이지만 막상 코드로 옮기기는 쉽지 않다. 나 또한 블로그에서 참조해 문제를 풀고 올렸다 ㅠ.ㅠ

Solution

class CombinationIterator {
    StringBuilder sb;
    String s;
    int len;
    HashMap<Character, Integer> hm;

    public CombinationIterator(String characters, int combinationLength) {
        this.sb = new StringBuilder();
        this.s = characters;
        this.len = combinationLength;
        this.hm = new HashMap<>();

        for(int i = 0; i<s.length(); i++){
            char c = s.charAt(i);
            if(sb.length() < len){
                sb.append(c);
            }

            hm.put(c, i);
        }
    }

    public String next() {
        String res = sb.toString();
        int ind = s.length() - 1;

        // 1. if sb consists of last characters of input, 
        //    delete all characters of input
        while(ind >= 0 && sb.length() != 0 && sb.charAt(sb.length() -1) == s.charAt(ind)){
            sb.deleteCharAt(sb.length() - 1);
            ind--;
        }

        if(sb.length() == 0){
            return res;
        }

        // 2. replace last character of sb to next character of it
        char c = sb.charAt(sb.length() - 1);
        ind = hm.get(c) + 1;
        sb.deleteCharAt(sb.length() - 1);

        // 3. fill characters of sb until length of sb is equal to combinationLength
        while(sb.length() < len && ind < s.length()){
            sb.append(s.charAt(ind));
            ind++;
        }

        return res;
    }

    public boolean hasNext() {
        return sb.length() != 0;
    }
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * String param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

Reference

https://leetcode.com/problems/iterator-for-combination/