Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Java Code Challenge: Wandering Fingers

DZone's Guide to

Java Code Challenge: Wandering Fingers

Software like Swype and SwiftKey lets smartphone users enter text by dragging their finger over the on-screen keyboard. Give two strings, find the possible words.

· Java Zone ·
Free Resource

Verify, standardize, and correct the Big 4 + more– name, email, phone and global addresses – try our Data Quality APIs now at Melissa Developer Portal!

The Java Code Challenge is a regular segment taking the best challenge from Reddit's dailyprogrammer. Things are a little different here, as we're focused purely on Java. A working solution is not enough; we're looking for the cleanest Java code with tests. Third-party libraries are welcome, but if you can do it without it will be easier for others to comprehend.

If you can fit your solution in the comments then go for it, but preferably put your answer in GitHub and link in the comments. Next week we'll be sharing the best solutions and sharing the best code practices we see!

Description

Software like Swype and SwiftKey lets smartphone users enter text by dragging their finger over the on-screen keyboard, rather than tapping on each letter.

Example image of Swype.

You'll be given a string of characters representing the letters the user has dragged their finger over.

For example, if the user wants "rest," the string of input characters might be "resdft" or "resert."

Input

Given the following input strings, find all possible output words of 5 characters or longer.

  1. qwertyuytresdftyuioknn
  2. gijakjthoijerjidsdfnokg

Output

Your program should find all possible words (5+ characters) that can be derived from the strings supplied.

Use http://norvig.com/ngrams/enable1.txt as your search dictionary.

The order of the output words doesn't matter.

  1. queen question
  2. gaeing garring gathering gating geeing gieing going goring

Notes/Hints

Assumptions about the input strings:

  • QWERTY keyboard.
  • Lowercase a-z only; no whitespace or punctuation.
  • The first and last characters of the input string will always match the first and last characters of the desired output word.
  • Don't assume users take the most efficient path between letters.
  • Every letter of the output word will appear in the input string.

Bonus

Double letters in the output word might appear only once in the input string, e.g. "polkjuy" could yield "polly".

Make your program handle this possibility.

Developers! Quickly and easily gain access to the tools and information you need! Explore, test and combine our data quality APIs at Melissa Developer Portal – home to tools that save time and boost revenue. Our APIs verify, standardize, and correct the Big 4 + more – name, email, phone and global addresses – to ensure accurate delivery, prevent blacklisting and identify risks in real-time.

Topics:
clean code ,code challenge ,java ,java 8

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}