CareerCup

here's a O(n*m) (n=no of words in the dictionary, m = max length of the word)complex solution with space O(52). Perform the following steps:
1. Take all the words from the lis with length same as the given word or +/- 1
2. Create a letter count array/map of the given word (for eg if the word is "coverage" then a=1, c=1, e=2, g=1, r=1, v=1) (say a[26] contains the letter count from a to z)
3. take each word from step 1. create its letter count array (say b[26]
4 for i = 1 to 26 sum += abs(a[i]-b[i]). each word with sum value = 1 or 2 will be the required word.

and i think my above solution will work for any difference just the sum value need to be modified

public List<string> FindWord(List<string> dictionary, string word)
{
List<string> output = new List<string>();

int[] charCount = new int[26];
char[] input = word.ToCharArray();

for (int i = 0; i < input.Length; i++)
{
charCount[input[i] - 'a']++;
}

int[] temp = new int[26];

foreach (string _word in dictionary)
{
if (Math.Abs(_word.Length - input.Length) == 1 || Math.Abs(_word.Length - input.Length) == 0)
{
charCount.CopyTo(temp, 0);

char[] _input = _word.ToCharArray();

for (int i = 0; i < _input.Length; i++)
{
temp[_input[i] - 'a']--;
}

int sum = 0;

for (int i = 0; i < temp.Length; i++)
{
sum += Math.Abs(temp[i]);
}

if (sum <= 2)
{
output.Add(_word);
}
}
}

return output;
}

How about a backtracking solution? Lets say we build a trie of the one million words. lets say input word is of length n. We check all the branches and keep track of number of mismatches and if mismatch count is less than permitted we allow traversing the trie else we exit the branch and check another branch using backtracking.

This approach however checks for words with only same length. I am checking how this can be modified to words with different length.

backtracking(root, "coverage", 1);

backtracking(trie node,string input_word, int mismatch_allowed)
{
    if (mismatch_allowed < 0)
        return;
    if (input_word.length == 0)
    {
        print current node details (i.e. complete word till this node);
        return;
    }

    for character_branch in (all_branches_at_root)
    {
        if (character_branch == input_word[0])
        {
             // first char matches, check next chars
             backtracking(character_branch_node, "overage", mismatch_allowed);
         }
         else {
             // character mismatch reduce the count
             backtracking(character_branch_node, "overage", --mismatch_allowed);
         }
    }
}

I think the key to solving this problem is to use the information that the list of words is sorted (i.e.: you already have the word list preprocessed to help you with the query).

Consider (for complexity computation):
N - number of words in the word list (max. 1 million)
L - size of a word (max. 40)
A - size of the alphabet (= 26)

For 1 letter distance you can use the following algorithm:
1. Generate all the possible words that are 1 letter distance away from the query word
- this has the complexity O(L*A)
2. Look up each of the generated words in the word list using a binary search:
- the look up of an individual word is O(L*logN)
- we have O(L*A) lookups => final complexity is O(L^2*A*logN) which is roughly (not considering the hidden constant) about 832.000 operations which is better than O(L*N) which is roughly 40 million operations.

For distance = 2, this algorithm performs worse than the O(L*N) version.

The question is more interesting and of practical use if the ordering of letters is important.

@anjana

In the algo presented by The Artist

a minor modification is needed such that it doesnt take into account of the words such as (sumit with sumitas)

what we can do is make the changes in that space i.e O(26)
for example the word sumit has to be searched
so s-1,u-1,m-1,i-1,t-1

when the word sumita is encountered all the fields in O(26) is zero except a which is -1,
so this is our word.

now if we take sumi , then only value corresponding to field t is -1.

but if we take a word such as samit then field corresponding to u would be 1 and a would be -1,

in a iteration corresponding to the word length there can be only a pair of 1 & -1;
we wont consider if there is 1&1 or -1 & -1 which might arise in the example of (umi or sumitaf) which would be the case for difference in length corresponding to 2.

We can solve the problem by the approach artist suggested. But we can reduce the time complexity from O(mn) to O((number of words with size+number of words with size-1+number of words with+1))m.

Simply apply the binary search on the list given to find the first occurance of the word with size-1, It would take O(logn)(i.e. log one million= approximately 20). From that index onwards you can traverse the list to until you reach a word with size+2. Since the list is already sorted, We don't need to traverse the entire list.

Couldn't get the part where sum=2...i mean if we find exact match, sum=0, differ by 1 then sum=1. How does sum=2 fit in. Please explain.

This might be a little dumb question but nonetheless, would be great if you would explain.

Couldn't get the part where sum=2...i mean if we find exact match, sum=0, differ by 1 then sum=1. How does sum=2 fit in. Please explain.

This might be a little dumb question but nonetheless, would be great if you would explain.