DailyProgrammer 284: Wandering Fingers

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.





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 5 characters or longer.

• qwertyuytresdftyuioknn

• 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.

• queen question

• 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

Problem 284

```
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;

namespace swipe
{
class Program
{
static string path = "C:\\Users\\px06\\Documents\\Visual Studio 2015\\Projects\\swipe\\swipe\\words.txt";
static void Main(string[] args)
{
string[] input = { "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews" };

string[] words = File.ReadAllLines(path);

var watch = System.Diagnostics.Stopwatch.StartNew();

foreach (string inp in input)
{
var acceptable = reduce(words, inp);

I'll review your code as written first then move onto the other questions.

It's the convention in C# to name all methods in PascalCase
reduce should be Reduce.

You're already using System.Diagnostics so you don't need to qualify the Stopwatch.StartNew() call.

input is a collection so should be pluralised (like you've done for words). It should be inputs.

foreach (string inp in input). Don't abbreviate your variable names, it just makes code harder to read with no benefit (in C# at least).

foreach(var input in inputs)
{

I've also used var here to demonstrate its usage. It can be used when the type of the assignment is obvious or when the exact type isn't important. I tend to use it everywhere if I'm honest.

This code is confusing:

var acceptable = reduce(words, inp);
foreach (int i in acceptable)
{

Without reading the implementation of reduce I have no idea what this code is about. Consider with more descriptive names:

foreach(var wordIndex in GetCandidateWordIndicies(words, input))
{

Now we're communicating what our code is doing without having to look at the implementation. Long and descriptive names are always preferable to short and ambiguous ones.

This would be better served by a for loop:

int count = 0;
foreach(string word in list)
{
    // stuff
    count++;
}

Like this:

for (var i = 0; i = 5 && input[0] == word[0] && input[input.Length - 1] == word[word.Length - 1])
    {
        acceptableList.Add(i);
    }
}

I'd also refactor the if to use First() and Last() (which are optimised implementations when the collection implements ICollection):

if (word.Length >= 5 
    && input.First() == word.First() 
    && input.Last() == word.Last())

That's a bit easier to skim.

In your check method charcheck should have been called currentPosition. I was initially confused by what you were doing and actually thought there may have been a bug with the ordering of the input letters.

Complexity

Your solution clearly depends on both size of the input dictionary (n) and the length of the input (m).

You loop over all words in the dictionary so your solution can't be any better than O(n).

Also you call input.IndexOf(c, charcheck);. I'm not 100% sure what the complexity of string.IndexOf is in C# but it's going to be related to the length of the string in some way - the naive implementation would be O(n*m) (m == 1` as you're searching 1 char at a time) worst case. Update: speculation confirmed by https://stackoverflow.com/a/2584204/1402923

That means your algorithm is definitely tied to both the size of the dictionary and the length of the input.

StackExchange Code Review Q#142784, answer score: 10