DailyProgrammer 284: Wandering Fingers

Question

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.

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

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);
                foreach (int i in acceptable)
                {
                    if (check(words[i], inp))
                    {
                        Debug.WriteLine(words[i]);
                    }
                }
            }
            watch.Stop();
            Console.WriteLine("Run time(ms): " + watch.ElapsedMilliseconds);
            Console.ReadLine();
        }

        static List<int> reduce(string[] list, string input)
        {
            List<int> acceptableList = new List<int>();
            int count = 0;
            foreach(string word in list)
            {
                if (word.Length >= 5 && input[0] == word[0] && input[input.Length - 1] == word[word.Length - 1])
                {
                    acceptableList.Add(count);
                }
                count++;
            }
            return acceptableList;
        }

        static bool check(string word, string input)
        {
            int charcheck = 0;

            foreach (char c in word)
            {
                charcheck = input.IndexOf(c, charcheck);
                if (charcheck == -1)
                {
                    return false;
                }
            }
            return true;
        }
    }
}

qwertyuytresdftyuioknn -> queen, question -> runtime: 2ms

gijakjthoijerjidsdfnokg
gaeing
garring
gathering
gating
geeing
gieing
going
goring
Run time(ms): 2

Trying a very complex string to see if I could find the word:

chlordiazepoxides

Input:

cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews

Output:

caches
cades
cafes
caffs
cages
caids
cairds
capes
caphs
capos
capotes
capouches
capuches
cards
cares
caress
carices
caries
carious
caroches
carps
carpus
carries
carroches
carrots
carrs
carryouts
cartes
cartouches
carts
carves
casefies
caseous
cases
casettes
cashes
cashews
cassettes
cassis
castes
castoffs
castors
casts
casus
catches
cates
catguts
catties
caucus
caves
cavies
cedes
cepes
cercis
cercus
ceres
ceriphs
cerites
ceros
cerous
certes
certifies
cetes
chads
chafes
chaffs
chairs
chaos
chapes
chaps
chards
chares
charges
chariots
charpoys
charros
charrs
chars
charts
chasers
chases
chassepots
chasses
chasseurs
chassis
chats
chaws
chayotes
chays
cheeps
cheerios
cheeros
cheers
chefs
cheroots
cherries
cherts
chess
cheths
chevies
chevres
chews
chias
chiaus
chichis
chics
chiders
chides
chiefs
chiggers
chigoes
chippies
chips
chiros
chirps
chirres
chirrs
chirrups
chits
chitters
chitties
chives
chivies
chivvies
chlorates
chlordiazepoxides
chlorides
chlorids
chlorites
chlorous
choices
choirs
choosers
chooses
chops
choragus
chordates
chords
choregus
chores
chorioids
chorizos
choroids
chorus
choruses
chorusses
choses
chotts
choughs
chousers
chouses
choushes
chows
christies
chrysophytes
chuddahs
chuddars
chudders
chufas
chuffs
chuggers
chugs
churches
churrs
chutes
chutists
ciders
cigars
circuits
circus
cires
cirrous
cirrus
cissies
cissoids
cists
cistus
citators
citers
cites
cities
citifies
citrates
citreous
citrous
citrus
citruses
civies
civvies
clachs
clades
clads
clags
claps
claries
clarifies
claroes
claros
clashes
clasps
class
classers
classes
classics
classifies
classis
clastics
clasts
claughts
claves
clavus
claws
clays
clefs
clefts
clepes
clergies
clerics
clerids
clerihews
clevis
clews
cliches
cliffs
clifts
clips
clitics
cloches
clods
cloggers
clogs
cloistress
cloots
clops
closeouts
closers
closes
closets
closures
clothes
cloths
clots
clotures
clouds
cloughs
clours
clouters
clouts
cloves
cloys
clozes
clues
clutches
clutters
coaches
coacts
coapts
coasts
coatees
coatis
coats
coaxes
coccids
coccus
codas
codders
codecs
coderives
coders
codes
codfishes
codgers
codices
codifies
codirects
codrives
coeds
coerces
coffeepots
coffees
coffers
coffrets
coffs
cogitates
cogitos
coiffes
coiffeurs
coiffures
coifs
coirs
coitus
coituses
cooches
cooees
cooers
cooeys
coofs
coops
coopts
cooters
cooties
coots
copes
copies
copihues
coppices
cordages
corders
cordgrass
cordgrasses
cordierites
cordites
cords
corduroys
corers
cores
corgis
corps
corpus
corrades
corrects
corridas
corridors
corries
corrodes
corrupts
corsacs
corsages
corsairs
corses
corsets
corteges
cortexes
cortices
corvees
corves
coryphees
cosecs
coses
cosets
coseys
coshes
cosies
cossets
costs
coteries
cotes
cotrustees
cottages
cottars
cottas
cotters
cottiers
cotypes
couches
cougars
coughs
coupes
coups
courages
courgettes
couriers
coursers
courses
courteous
courters
courtiers
courts
courtsides
courtyards
couters
couths
coutures
coves
coxes
coydogs
coyotes
coypous
coypus
cozes
cozeys
cozies
cozzes
crafts
crags
crapes
crappies
craps
crases
crashes
crasis
crass
cratches
crates
craves
craws
crazes
crazies
creches
creeds
creepies
creeps
crepes
cress
cretics
crews
criers
cries
cripes
crises
crisis
crisps
critics
critters
critturs
crocs
crocus
crofts
croppies
crops
crores
cross
crouches
crows
cruces
crudes
crudites
cruds
cruets
cruisers
cruises
cruors
crusades
cruses
crusets
crushes
crusts
crutches
cruxes
crypts
cuddies
cuffs
cuifs
cuirass
cuirasses
cuishes
cuisses
cupids
curacies
curaghs
curares
curaris
curassows
curates
curatives
curators
curches
curds
curers
cures
curets
curettes
curfews
curfs
curies
curios
curious
curites
currachs
curraghs
currieries
curriers
curries
currs
cursers
curses
cursives
cursors
curtseys
curtsies
curves
cuscus
cusecs
cuspides
cuspids
cuspis
cusps
cussers
cusses
cussos
custodes
custos
cutches
cutes
cuteys
cutgrass
cutgrasses
cuties
cutis
cutises
cutoffs
cutouts
cuttages
cutters
cutties
cutups
cyders
cypres
cypress
cystoids
cysts
Run time(ms): 5

I just wanted to see what I can improve on my code. I'm very new to C# so I'd like some suggestions on what I can do to either improve efficiency or improve it in general. For the most part it looks like it works well, but could I improve this any further? Is there anything else I could add to make it even faster?

Would anyone know the efficiency of this program? I have a feeling it's \$O(\log n)\$ but obviously that shouldn't be the case by looking at the structure.

I tried feeding in 1,000,000 randomly generated characters and here is the output:

zaikai
zamindari
zastrugi
zecchini
zingani
zingari
zombi
zucchini
Run time(ms): 2

I know that the runtime is significantly decreased by cutting down the dictionary by the first index of the word word[0] == dict[word[0]] and then the last element word[last] == dict[word[last]], so what factors here would determine speed? The only ones I can think of are: size of dictionary and location of the first char (i.e. starting with a z). Even the input size doesn't determine the runtime, so the complexity isn't increasing even though I am trying to find a match in check().

That being said, Visual Studio is using up to 27 MB of RAM while computing the 1M long string... but who really cares about space-complexity?

Answer 1

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 < list.Count; i++)
{
    var word = list[i];
    if (word.Length >= 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.

Answer 2

Just a little tip, no full review.

You can escape the tedious escaping of the escape character in a string literal by putting an @ in front of it:

string path = "C:\\Users\\px06\\...";

becomes

string path = @"C:\Users\px06\...";

The rest of both lines were omitted for brevity.

Answer 3

1. Always specify access modifiers,

2. Follow the .Net naming guidelines, methods and namespaces are PascalCase

3. RobH beat me to the rest of the usual cosmetic stuff.

When it comes to performance there may be a lot to gain from constructing a map from [FirstCharacter, LastCharacter] -> CandidateWord. Constructing such a mapping is not free but if you parse multiple inputs it will be worth it.

You can construct the map using Linq:

var words = File.ReadAllLines(path);
var wordLookup = words.Where(word => word.Length >= 5)
                      .GroupBy(word => word[0])
                      .ToDictionary(group => group.Key, group => group.ToLookup(w => w[w.Length - 1]));

Dictionary and Lookup are hash-based maps that provide constant time lookup (terms and conditions may apply).

And then you can find candidates by using a helper:

private static IEnumerable<string> GetCandidateWords(string input, Dictionary<char, ILookup<char, string>> candidateLookup)
{
    var firstChar = input[0];
    var lastChar = input[input.Length - 1];
    var maxLength = input.Length;
    return candidateLookup[firstChar][lastChar].Where(w => w.Length <= maxLength);
}

And then you filter out the valid words:

public static IEnumerable<string> GetValidWords(this string input, Dictionary<char, ILookup<char, string>> candidateLookup)
{
    var candidateWords = GetCandidateWords(input, candidateLookup);
    return candidateWords.Where(candidate => ValidateCandidateWord(input, candidate));
}

And your check now renamed to be more explicit about it's function:

private static bool ValidateCandidateWord(string input, string word)
{
    int searchFrom = 0;
    foreach(var c in word)
    {
        var currentIndex = input.IndexOf(c, searchFrom);
        if(currentIndex == -1)
        {
            return false;
        }
        searchFrom = currentIndex + 1;
    }

    return true;
}

I changed it to search from the next character on, this means queen is no longer a valid option from qwertyuytresdftyuioknn as there is only a single e after the first u. I can't tell which way is correct from the spec so this is based on opinion.

If you put all the methods in a static class you end up with an extension method on string:

public static class StringSwipeExtentions
{
    private static IEnumerable<string> GetCandidateWords(string input, Dictionary<char, ILookup<char, string>> candidateLookup)
    {
        var firstChar = input[0];
        var lastChar = input[input.Length - 1];
        var maxLength = input.Length;
        return candidateLookup[firstChar][lastChar].Where(w => w.Length <= maxLength);
    }

    public static IEnumerable<string> GetValidWords(this string input, Dictionary<char, ILookup<char, string>> candidateLookup)
    {
        var candidateWords = GetCandidateWords(input, candidateLookup);
        return candidateWords.Where(candidate => ValidateCandidateWord(input, candidate));
    }

    private static bool ValidateCandidateWord(string input, string word)
    {
        int searchFrom = 0;
        foreach(var c in word)
        {
            var currentIndex = input.IndexOf(c, searchFrom);
            if(currentIndex == -1)
            {
                return false;
            }
            searchFrom = currentIndex + 1;
        }

        return true;
    }
}

And you using it:

public static void Main()
{
    var inputs = new[]
    { 
        "qwertyuytresdftyuioknn",
        "gijakjthoijerjidsdfnokg",
        "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews"
    };

    var words = File.ReadAllLines(path);
    var wordLookup = words.Where(word => word.Length >= 5)
                          .GroupBy(word => word[0])
                          .ToDictionary(group => group.Key, group => group.ToLookup(w => w[w.Length - 1]));

    foreach(var input in inputs)
    {
        var stopwatch = System.Diagnostics.Stopwatch.StartNew();
        var validWords = input.GetValidWords(wordLookup);
        stopwatch.Stop();
        Console.WriteLine("{0} done in {1}ms, valid words:", input, stopwatch.ElapsedMilliseconds);
        foreach(var validWord in validWords)
        {
            Console.WriteLine(validWord);
        }
    }
}

Answer 4

Since your programm should only find words with 5 or more characters, you could filter out words that have less characters. This will reduce the amount of loaded words.

For this purporse you can use File.ReadLines with a Linq-statement.

int minimumWordLength = 5;

HashSet<string> words = new HashSet<string>();
foreach (string line in File.ReadLines(path).Where(p=>p.Length >= minimumWordLength))
{
    words.Add(line);
}

Using ReadLines and Linq the amount of words can be reduced even more, since you are only interested in words that

The first and last characters of the input string will always match the first and last characters of the desired output word

string input = "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews";
int minimumWordLength = 5;
string firstChar = input[0].ToString();
string lastChar = input[input.Lenght-1].ToString();

foreach (string line in File.ReadLines(path)
                            .Where(p=>p.Length >= minimumWordLength)
                            .Where(p=>p.StartsWith(firstChar) && p.EndsWith(lastChar)))
{
    words.Add(line);
}

This changes would make your reduce method obsolete and you can directly check the words with your method check.

Answer 5

You algorithm is - in my opinion - good, but you could check the candidates in one operation in a Filter function as shown below.

I have modified your solution with some comments below:

  // Changed to static because it implements an extension to IEnumerable<string>
  static class Program
  {
    // use @ to get rid of the \\ as another commentor explained
    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)
      {
        foreach (var validWord in words.Filter(inp))
        {
          Console.WriteLine(validWord);
        }
      }

      watch.Stop();
      Console.WriteLine("Run time(ms): " + watch.ElapsedMilliseconds);
      Console.ReadLine();
    }

    // This is combining reduce() and check() in one iteration
    static IEnumerable<string> Filter(this IEnumerable<string> words, string input)
    {
      foreach (string word in words)
      {
        // calling check() at the same time
        if (word.Length >= 5 && input[0] == word[0] && input[input.Length - 1] == word[word.Length - 1] && check(word, input))
        {
          yield return word;
        }
      }
    }

    static bool check(string word, string input)
    {
      int charcheck = 0;

      foreach (char c in word)
      {
        charcheck = input.IndexOf(c, charcheck);
        if (charcheck == -1)
        {
          return false;
        }
      }
      return true;
    }
  }

You could even skip the Filter function and gain the same with a Where() like:

  // Changed to static because it implements an extension to IEnumerable<string>
  static class Program
  {
    // use @ to get rid of the \\ as another commentor explained
    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)
      {
        foreach (var validWord in words.Where(word => word.Length >= 5 && inp[0] == word[0] && inp[inp.Length - 1] == word[word.Length - 1] && check(word, inp)))
        {
          Console.WriteLine(validWord);
        }
      }

      watch.Stop();
      Console.WriteLine("Run time(ms): " + watch.ElapsedMilliseconds);
      Console.ReadLine();
    }

    static bool check(string word, string input)
    {
      int charcheck = 0;

      foreach (char c in word)
      {
        charcheck = input.IndexOf(c, charcheck);
        if (charcheck == -1)
        {
          return false;
        }
      }
      return true;
    }
  }

If you store the words in a dictionary you can gain a couple of ms in performance and your n in O(n*m) would be reduced a bit. Dictionary is close to O(1):

  // Changed to static because it implements an extension to IEnumerable<string>
  static class Program
  {
    // use @ to get rid of the \\ as another commentor explained
    static string path = @"C:\\Users\\px06\\Documents\\Visual Studio 2015\\Projects\\swipe\\swipe\\words.txt";

    static void Main(string[] args)
    {
      string[] input = { "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews", "ardidtrwekfsisuklms" };
      var words = File.ReadAllLines(path).GroupBy(str => str[0]).ToDictionary(gr => gr.Key);

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

      foreach (string inp in input)
      {
        foreach (var validWord in words[inp[0]].Where(word => word.Length >= 5 && inp[0] == word[0] && inp[inp.Length - 1] == word[word.Length - 1] && check(word, inp)))
        {
          Console.WriteLine(validWord);
        }

        Console.WriteLine();
      }

      watch.Stop();
      Console.WriteLine("Run time(ms): " + watch.ElapsedMilliseconds);
      Console.ReadLine();
    }

    static bool check(string word, string input)
    {
      int charcheck = 0;

      foreach (char c in word)
      {
        charcheck = input.IndexOf(c, charcheck);
        if (charcheck == -1)
        {
          return false;
        }
      }
      return true;
    }
  }

Answer 6

I started to refactor the original code, but using a class just made sense. A class for MajicWord makes it easier to expand. Getting the middle characters would be more difficult. Using GetHashCode() for the Dictionary Key makes sense.

This is about 40x as fast as your solution (runs in 5 ms)
Uses a Dictionary with a Key of first and last letter
So lookup to the candidates (matching first and last) is \$O(1)\$
On the candidates it iterates on middle (pretty minor)
Depends on a class called MajicWord for the heavy lifting

{
    static void Main(string[] args)
    {
        string wordToMatch = "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews";
        Stopwatch sw = new Stopwatch();
        sw.Start();
        List<string> wordMatches = WordMatches(wordToMatch); /*quen*/
        sw.Stop();
        //foreach (string s in wordMatches)
        //    Console.WriteLine(s);
        Console.WriteLine(string.Join(", ", wordMatches));
        Console.WriteLine("milliseconds first pass is high as has to build dictionary");
        Console.WriteLine("milliseconds  me " + sw.ElapsedMilliseconds.ToString() + Environment.NewLine);
        Console.ReadLine();
    }
    private static Dictionary<Int32, List<MajicWord>> wordSet;
    public static List<string> WordMatches(string input)
    {
        if (wordSet == null)
        {
            wordSet = new Dictionary<Int32, List<MajicWord>>();
            try
            {   // Open the text file using a stream reader.
                string line;
                using (StreamReader sr = new StreamReader(@"words.txt"))
                {
                    while ((line = sr.ReadLine()) != null)
                    {
                        if (line.Length < 5)
                            continue;
                        //Debug.WriteLine(line);
                        MajicWord mw = new MajicWord(line);
                        if (!wordSet.ContainsKey(mw.GetHashCode()))
                            wordSet.Add(mw.GetHashCode(), new List<MajicWord>());
                        wordSet[mw.GetHashCode()].Add(mw);
                    }
                }
            }
            catch (Exception e)
            {
                Console.WriteLine("The file could not be read:");
                Console.WriteLine(e.Message);
            }
            //foreach (List<MajicWord> lmw in wordSet.Values)
            //    Debug.WriteLine(lmw.Count.ToString());
            Debug.WriteLine("end ctro");
        }
        Stopwatch sw = new Stopwatch();
        sw.Start();
        List<string> wordMatches = new List<string>();
        MajicWord wtm = new MajicWord(input);
        List<MajicWord> candidates = wordSet[wtm.GetHashCode()];
        IEnumerable<MajicWord> matches = candidates.Where(x => x.IsMatchOrder(wtm));
        foreach (MajicWord mw in matches.OrderBy(x => x.Word))
            wordMatches.Add(mw.Word);
        sw.Stop();
        Console.WriteLine("milliseconds WordMatches " + sw.ElapsedMilliseconds.ToString() + Environment.NewLine);
        return wordMatches;
    }
}

public class MajicWord
{
    public override bool Equals(Object obj)
    {
        if (!(obj is MajicWord)) return false;

        MajicWord mw = (MajicWord)obj;
        return (string.Compare(mw.Word, this.Word, true) == 0);
    }
    public override int GetHashCode()
    {
        return (int)CharFirst * 17 ^ (int)CharLast;
        //((int)CharFirst - 97)*26 + (int)CharLast - 97; this hashes better for a-z
    }
    public bool IsMatch(MajicWord mwm)
    {
        if (mwm.GetHashCode() != this.GetHashCode())
            return false;
        return (this.MiddleHash).IsSubsetOf(mwm.MiddleHash);
    }
    public bool IsMatchOrder(MajicWord mwm)
    {
        //if (!IsMatch(mwm))  // this slowed it down
        //    return false;

        if (mwm.GetHashCode() != this.GetHashCode())
            return false;

        if (this.Word.Length > mwm.Word.Length)
            return false;

        int charcheck = 0;
        foreach (char c in this.WordMiddle)
        {
            charcheck = mwm.WordMiddle.IndexOf(c, charcheck);
            if (charcheck == -1)
            {
                return false;
            }
        }
        return true;
    }
    public string Word { get; private set; }
    private string wordMiddle = null;
    public string WordMiddle
    {
        get
        {
            if(wordMiddle == null)
            {
                StringBuilder sb = new StringBuilder();
                for (int i = 1; i < Word.Length - 1; i++)
                    sb.Append(Word[i]);
                wordMiddle = sb.ToString();
            }
            return wordMiddle;
        }
    }
    public char CharFirst { get; private set; }
    public char CharLast { get; private set; }
    HashSet<char> middleHash = null;
    public HashSet<char> MiddleHash
    {   
        get
        {
            if(middleHash == null)
            {
                middleHash = new HashSet<char>();
                for (int i = 1; i < Word.Length - 1; i++)
                    middleHash.Add(Word[i]);
            }
            return middleHash;
        }
    }
    public MajicWord(string word)
    {
        if (word.Length < 2)
            throw new IndexOutOfRangeException();
        Word = word.ToLower();
        CharFirst = Word[0];
        CharLast = Word[Word.Length-1];
    }
}