Over a million developers have joined DZone.

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

Check out this 8-step guide to see how you can increase your productivity by skipping slow application redeploys and by implementing application profiling, as you code! Brought to you in partnership with ZeroTurnaround.

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.

The Java Zone is brought to you in partnership with ZeroTurnaround. Check out this 8-step guide to see how you can increase your productivity by skipping slow application redeploys and by implementing application profiling, as you code!

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

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

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

{{ parent.tldr }}

{{ parent.urlSource.name }}