Thread: Optimizing algorithm to find "distance" between two strings

Hi,
I'm trying to solve this problem:

The typical touchscreen keyboard looks like this:


qwertyuiop
asdfghjkl
zxcvbnm




You should use the distance between the letters to type a word: the distance is the sum of the horizontal and vertical distance between the typed and proposed letter. Assume you typed a w, the distance to e is 1, while the distance to z is 3.


The typed word and the list of words from the spell checker all have the same length. The distance between two words is the sum of the letter distances. So the distance between ifpv and icpc is 3.

Even if the code works it's of course pretty slow because everytime I'm searching for the position of the character in the table. So I'd like to know how could I improve it, even if it's needed to rewrite it from zero.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


typedef struct
{
    int x;
    int y;
} my_coordinate;


static char *look_up_table[3] = {"qwertyuiop",
                                 "asdfghjkl",
                                 "zxcvbnm"  };
                 


static my_coordinate search_ch(int ch)
{
    int i;
    my_coordinate ch_pos = { .x = -1, .y = -1 };
    char *found_ch = NULL;
    for(i = 0; i < 3; ++i)
    {
        found_ch = strchr(look_up_table[i], ch);
        if(found_ch != NULL)
        {
            ch_pos.x = i;
            ch_pos.y = found_ch - look_up_table[i];     /*This difference return the index in the string of the charachter*/
        }
    }


    return ch_pos;
}


static int get_distance(const char *s, const char *p)
{
    int distance = 0;
    my_coordinate ch_s;
    my_coordinate ch_p;


    while(*s != '\0')   /* s and p always have the same length*/
    {
        ch_s = search_ch(*s); 
        ch_p = search_ch(*p);
        distance += abs(ch_s.x - ch_p.x) + abs(ch_s.y - ch_p.y);
        s++; p++;
    }


    return distance;
}






int main(void)
{
    const char *s = "ifpv";
    const char *p = "iopc";


    printf("%d\n", get_distance(s, p));
    
    return EXIT_SUCCESS;
}

Thank you, I'm going to try it with the full code and see how it goes!