current position:Home>leetcode 1286. Iterator for Combination(python)

leetcode 1286. Iterator for Combination(python)

2022-01-31 14:14:30 Wang Daya

「 This is my participation 11 The fourth of the yuegengwen challenge 15 God , Check out the activity details :2021 One last more challenge

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

analysis

According to the meaning , To design a CombinationIterator class , It needs to include several functions :

  • CombinationIterator(string characters, int combineLength) Use a string of different lowercase letters that have been sorted characters And number combinationLength Initialize the object as a parameter
  • next() The length returned in dictionary order is combinationLength Next combination of
  • hasNext() Returns if and only if there is a next combination true

The key to this problem is to find all the combinations , as for next and hasNext The two functions only need to make simple logical judgment , The first method uses built-in functions itertools.combinations To find all the lengths combinationLength The combination of , 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 code 

Running results

Runtime: 44 ms, faster than 81.82% of Python online submissions for Iterator for Combination.
Memory Usage: 16 MB, less than 72.73% of Python online submissions for Iterator for Combination.
 Copy code 

analysis

Of course, the use of built-in functions is not horizontal , We can also write our own code , Custom function permute Use DFS Find all the 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 code 

Running results

Runtime: 52 ms, faster than 54.55% of Python online submissions for Iterator for Combination.
Memory Usage: 15.9 MB, less than 72.73% of Python online submissions for Iterator for Combination.
 Copy code 

Original link :leetcode.com/problems/it…

Your support is my greatest motivation

copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201311414284352.html

Random recommended