LeetCode 5087: Letter Tile Possibilities in Swift

Image for post
Image for post

This is a scrabble challenge. What are the different combinations of letters that can be derived from a set of letters.

For example with input tiles of “AAB” there are the following possibilities:

“A”

“B”

“AA”

“AB”

“BA”

“AAB”

“ABA”

“BAA”

Note that there are no repetitions for the tile possibilities here!

Dictionaries

Dictionaries in Swift typically have a lookup of O(1). This makes it a good candidate for this problem.

The setup

We can place each of our tiles into a frequency array, and can use the great initializer in Swift that allows us to give a default for each tile (making the syntax easy to read):

The algorithm

This algorithm for the input “AAB” is as follows:

We put the tiles into the frequency table -

freq = [“A”: 2, “B”: 1]

for the first letter we can either pick A or B.

so the two possibilities return:

Case A:

freq = [“A”: 1, “B”: 1]

or

Case B:

freq = [“A”: 2, “B”: 0]

In either case we iterate through the elements remaining in the array. For each element in turn we remove it from the dictionary, and recurse on this new dictionary.

After we have finished, we need to replace the tile into the dicionary. In Swift this looks like:

The result

The runtime is fast, but over time this may be beaten by other contributions (who knows?)

Image for post
Image for post

Want to get in contact? Try the link here:

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store