“This is the 15th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

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
Copy the code

Note:

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

parsing

Design a CombinationIterator class, which should contain several functions:

  • CombinationIterator(string characters, Int combineLength) initializes the object using the characters string and number combinationLength that have been sorted with different lowercase letters
  • Next () returns the next combination of length combinationLength, in lexicographical order
  • HasNext () returns true if and only if the next combination exists

The first method uses the built-in function itertools.combinations to find all combinations of length combinationLength. Simple and crude.

answer

class CombinationIterator(object):

    def __init__(self, characters, combinationLength):
        """
        :type characters: str
        :type combinationLength: int
        """
        self.characters = characters
        self.L = [''.join(i) for i in itertools.combinations(characters, combinationLength)]
        

    def next(self):
        """
        :rtype: str
        """
        return self.L.pop(0)
        
        
    def hasNext(self):
        """
        :rtype: bool
        """
        if self.L:
            return True
        return False
        

        	      
		
Copy the code

The results

Given in the Python online submissions for Iterator for Combination. Memory Usage: 10 MB, less than 72.73% of Python online submissions for Iterator for CombinationCopy the code

parsing

Of course, using the built-in function is not superior, we can also write our own code, custom permute use DFS to find all combinations.

answer

class CombinationIterator(object):

    def __init__(self, characters, combinationLength):
        """
        :type characters: str
        :type combinationLength: int
        """
        self.characters = characters
        self.n = combinationLength
        self.N = len(characters)
        self.L = []
        self.permute('', 0)
    
    def permute(self, s, start):
        if len(s) == self.n:
            self.L.append(s)
            return
        else:
            for i in range(start, self.N):
                self.permute(s + self.characters[i], i + 1)

    def next(self):
        """
        :rtype: str
        """
        return self.L.pop(0)
        
        
    def hasNext(self):
        """
        :rtype: bool
        """
        if self.L:
            return True
        return False
Copy the code

The results

Given in Python online submissions for Iterator for Combination. Given in the Python online submissions for Iterator for Combination.Copy the code

Original link: leetcode.com/problems/it…

Your support is my biggest motivation