words_in_phone_number

package
v0.0.0-...-86b9fec Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Apr 25, 2022 License: MIT Imports: 3 Imported by: 0

README

Words In Phone Number

If you open the keypad of your mobile phone, it'll likely look like this:

   ----- ----- -----
  |     |     |     |
  |  1  |  2  |  3  |
  |     | abc | def |
   ----- ----- -----
  |     |     |     |
  |  4  |  5  |  6  |
  | ghi | jkl | mno |
   ----- ----- -----
  |     |     |     |
  |  7  |  8  |  9  |
  | pqrs| tuv | wxyz|
   ----- ----- -----
        |     |
        |  0  |
        |     |
         -----

Almost every digit is associated with some letters in the alphabet; this allows certain phone numbers to spell out actual words. For example, the phone number 2536368 can be written as clement; similarly, the phone number 2686463 can be written as antoine or as ant6463.

It's important to note that a phone number doesn't represent a single sequence of letters, but rather multiple combinations of letters. For instance, the digit 2 can represent three different letters (a, b, and c).

You're given a stringified phone number of any non-zero length and a non-empty list of lowercase english-alphabet words.

Write a function that returns the list of words that can be found in the phone number. The final words don't need to be in any particular order.

Note that you should rely on the keypad illustrated above for digit-letter associations.

Sample Input

phoneNumber = "3662277"
words = ["foo", "bar", "baz", "foobar", "emo", "cap", "car", "cat"]

Sample Output

["bar", "cap", "car", "emo", "foo", "foobar"] 
// The words could be ordered differently.

Documentation

Index

Constants

This section is empty.

Variables

View Source
var DigitLetters = map[rune][]rune{
	'0': {},
	'1': {},
	'2': {'a', 'b', 'c'},
	'3': {'d', 'e', 'f'},
	'4': {'g', 'h', 'i'},
	'5': {'j', 'k', 'l'},
	'6': {'m', 'n', 'o'},
	'7': {'p', 'q', 'r', 's'},
	'8': {'t', 'u', 'v'},
	'9': {'w', 'x', 'y', 'z'},
}
View Source
var LetterDigits = map[rune]rune{
	'a': '2',
	'b': '2',
	'c': '2',
	'd': '3',
	'e': '3',
	'f': '3',
	'g': '4',
	'h': '4',
	'i': '4',
	'j': '5',
	'k': '5',
	'l': '5',
	'm': '6',
	'n': '6',
	'o': '6',
	'p': '7',
	'q': '7',
	'r': '7',
	's': '7',
	't': '8',
	'u': '8',
	'v': '8',
	'w': '9',
	'x': '9',
	'y': '9',
	'z': '9',
}

Functions

func WordsInPhoneNumber

func WordsInPhoneNumber(phoneNumber string, words []string) []string

WordsInPhoneNumber O(n^2 + m * w) time | O(n^2 + m * w) space - where n is the length of the phone number, m is the number of words, and w is the length of the longest word

Types

type ModifiedSuffixTrie

type ModifiedSuffixTrie map[byte]ModifiedSuffixTrie

func NewModifiedSuffixTrie

func NewModifiedSuffixTrie() ModifiedSuffixTrie

func (ModifiedSuffixTrie) Contains

func (trie ModifiedSuffixTrie) Contains(str string) bool

Contains O(m) time | O(1) space

func (ModifiedSuffixTrie) PopulateModifiedSuffixTrieFrom

func (trie ModifiedSuffixTrie) PopulateModifiedSuffixTrieFrom(str string)

PopulateModifiedSuffixTrieFrom O(n^2) time | O(n^2) space

type Trie

type Trie struct {
	// contains filtered or unexported fields
}

func (Trie) Add

func (t Trie) Add(word string)

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL