EPIC1307 - Subwords
Subwords is a game wherein you are given a word and must find all possible rearrangements of the letters that form English words. Not all letters need be used. For example, if you're given the word "computer" then four possible subwords are:
- Court
- Outer
- Truce
- Pure
Given an input word and a list of dictionary words, return the total number of valid subwords found.
Note that a word is not considered a subword of itself. For example, with the input "computer" if you find "computer" in the dictionary then it should not be counted.
Additionally, a subword should not be counted twice if there are multiple ways to form that word. For example, if your word is balloon then you should not count the word "on" twice using each 'o'. It should be counted only once.
Input
The first string input is the starting word. All remaining strings are the dictionary. You should ignore any blank lines. Note that you may need to be able to handle a long list of words (tens of thousands).
Output
The number of subwords found in the dictionary.
Example
Input: computer
aardvark
computer
court
outer
pure
truce
wish
Output: 4
hide comments
nadstratosfer:
2018-06-26 05:54:43
Words contain uppercase characters and punctuation. |
Added by: | BYU Admin |
Date: | 2013-03-20 |
Time limit: | 2s-10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |