Return a list of words from a given dictionary that match T9 (e.g. 2=ABC, 3=DEF) input using a suffix trie

t9-suffixtrie.js

/**
 * Given an int[], dictionary of words, and function that returns letters corresponding to a number (as on a phone),
 * return a list of possible words from the numbers given.
 */
var dictionary = ['FOO', 'BAR', 'BAY', 'BAZ', 'QUX'];
 
function parseT9(input, trie, partialWord, words) {
    // Avoid Naive O(3^n) solution
    if (!input.length) return words;

    // Initialize here for nicer API
    // First, construct a suffix trie from dictionary.
    if (trie === undefined) trie = constructSuffixTrie(dictionary);
    if (partialWord === undefined) partialWord = '';
    if (words === undefined) words = [];
    
    var letters = t9(input.shift());
    letters.forEach(function(letter) {
        if (trie[letter] != null) {
            if (trie[letter] === '') {
                words.push(partialWord + letter);
            } else {
                parseT9(input, trie[letter], partialWord + letter, words);
            }
        }
    });
    return words;
}

Object.clone = function clone(obj) {
    if(obj == null || typeof(obj) != 'object')
        return obj;

    var temp = obj.constructor(); // changed

    for(var key in obj) {
        temp[key] = clone(obj[key]);
    }
    return temp;
};

Object.extend = function extend(destination, source) {
  for (var property in source) {
    if (source[property] && source[property].constructor && source[property].constructor === Object) {
      destination[property] = destination[property] || {};
      arguments.callee(destination[property], source[property]);
    } else {
      destination[property] = source[property];
    }
  }
  return destination;
};

// Assume each entry is valid
function constructSuffixTrie(dictionary) {
    var trie = {};
    
    dictionary.forEach(function addLeaf(entry) {
        function buildPath(obj, charArray) {
            if (charArray.length === 1) {
                var t = {}
                t[charArray[0]] = '';
                return t;
            }
            var parent = charArray.shift();
            obj[parent] = buildPath(Object.clone(obj), charArray);
            return obj;
        }
        Object.extend(trie, buildPath({}, entry.split('')));
    });
    return trie;
}

function t9(num) {
    switch(num) {
        case 2: return ['A', 'B', 'C'];
        case 3: return ['D', 'E', 'F'];
        case 4: return ['G', 'H', 'I'];
        case 5: return ['J', 'K', 'L'];
        case 6: return ['M', 'N', 'O'];
        case 7: return ['P', 'Q', 'R', 'S'];
        case 8: return ['T', 'U', 'V'];
        case 9: return ['W', 'X', 'Y', 'Z'];
        case 0: return [' ', ',', '.'];
        default: throw new Error('Invalid key pressed for T9');
    }
}

parseT9([2,2,9]);