0 ms C solution; O(n) time and O(1) space using Direct Address Tables.


  • 0
    N
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    char** findWords(char** words, int wordsSize, int* returnSize) 
    {
        char** legal_words = (char**)calloc(wordsSize, sizeof(char*));
        char rows[3][11] = {
            "qwertyuiop",
            "asdfghjkl",
            "zxcvbnm"
        };
        
        
        // Ascii codes range from [0, 255]. A direct address table is essentially a hash table with h(key) = key. Hence we can index directly into the lookup table using the ascii code. It takes constant time to set up these tables.
        int char_sets[3][256] = {0};
        
        for (int i=0; i<3; i++)
        {
            char* row = rows[i];
            int* cset = char_sets[i];
            while (*row)
            {
                cset[*row] = 1;
                cset[*row - 'a' + 'A'] = 1;
                row++;
            }
        }
        
        // Iterate over words to find legal words.
        *returnSize = 0;
        for (int i=0; i<wordsSize; i++)
        {
            char* rhead = words[i];
            int* cset = NULL;
            // Find the row that the first character belongs to.
            for (int j=0; j<3; j++)
                if (char_sets[j][*rhead])
                    cset = char_sets[j];
            // Do rest of the characters belong to the same row?
            bool legal = true;   
            while (*rhead)
            {
                if (!cset[*rhead]) 
                {
                    legal = false;
                    break;
                }
                rhead++;
            }
            // All good. Append this word to response set.
            if (legal)
            {
                legal_words[*returnSize] = words[i];
                *returnSize += 1;
            }
        }
        
        return legal_words;
    }
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.