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

The CMS developers love. Open Source, API-first and Enterprise-grade. Try BloomReach CMS for free.

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.

BloomReach CMS: the API-first CMS of the future. Open-source & enterprise-grade. - As a Java developer, you will feel at home using Maven builds and your favorite IDE (e.g. Eclipse or IntelliJ) and continuous integration server (e.g. Jenkins). Manage your Java objects using Spring Framework, write your templates in JSP or Freemarker. Try for free.

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 }}