I've implemented C++'s
std::includes algorithm in Python, so that I can use it to efficiently implement a Scrabble "can I make this word" function:
def word_can_be_made_from_rack(word, rack): return set_includes(sorted(rack), sorted(word))
Here's the implementation, with some test cases:
def set_includes(haystack, needle): j = 0 hn = len(haystack) for c in needle: while j != hn and haystack[j] < c: j += 1 if j == hn: return False if haystack[j] > c: return False j += 1 return True assert set_includes('abcdef', 'af') assert set_includes('abcdef', 'bce') assert set_includes('abcdef', 'abcdef') assert set_includes('aaaaa', 'a') assert set_includes('aaaaa', 'aa') assert set_includes('aaaaax', 'ax') assert set_includes('abbbcxx', 'abc')
This is similar to Find if one list is a subsequence of another except that it assumes (and requires) that the two input strings are sorted.
The manual management of index
j in this code doesn't feel very Pythonic. Am I missing an easier way to write this algorithm?
itertools one-liners will be accepted as answers, especially if they're more performant. :)