JavaScript Prefix Match (Dictionary Application)

Recently I have a dictionary web application which needs to find prefix-matched words in an array of strings. Here is the specification of my problem:

Input: Given a set of strings (words), and an user input string

Output: a set of strings with prefix the same as the user input string

My naive solution is as follows: Because the set of given strings are huge, we first group them by the first letter of the string. For example, string with prefix a goes to first group, and strings with prefix b goes to second group, etc. Then we use the user input sting to match the prefix of strings in the group by JavaScript String indexOf() Method. We don't need to search the entire given strings. We just need to search the corresponding group which has the same prefix as the user input string. This can save a lot of time, at the cost of some additional space and code. If more efficient solution is needed, try Radix tree to make your search faster [4].

The following is the demo and sample code of the naive solution I just mention. Type some word that starts with a, b, or c in the demo, and you will see the result.

Demo

Source Code for Demo (HTML):

naive.html | repository | view raw 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
<!doctype html>
<html>
<head>
  <meta charset="utf-8">
  <title>JavaScript Dictionary Prefix Match - Naive Solution</title>
  <!-- This example shows how to find prefix matched words in a set of words -->
</head>
<body onload="document.getElementById('Text1').focus();">

 <div style="text-align: center">
  <input id="Text1" type="text" style="font-family: arial;"
         onpropertychange="javascript:strMatch();" oninput="javascript:strMatch();"/>
  <input id="Button1" type="button" value="look up" />
 </div>
 <br /><br />
 <div id="userInput" style="text-align: center;"></div><br />
 <div id="result" style="text-align: center;"></div>

<script src="naive.js"></script>
</body>
</html>

Source Code for Demo (JavaScript):

naive.js | repository | view raw 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
words_prefix_a = ["adwihjd", "aruwdn", "aeiuiwond", "aehuwgd", "aowqmgfv", "awqnmfwxsa", "aqgwqvsa", "aansqnsoq", "awqgwqenjio"];
words_prefix_b = ["bsaiuhw", "baww", "bahxnbzd", "bsqomzxb", "bbsjqbsoq", "bcsihwio", "bjaskdka", "baoshdsji", "bdaiohwi"];
words_prefix_c = ["csjioqjs", "ccwjiow", "csjqios", "cakopwd", "cdjiowhj", "ctjioend", "ckihsiow"];

function strMatch() {
  /* remove whitespace in the beginning and end of the string */
  var userInputStr = document.getElementById("Text1").value.replace(/(^\s+)|(\s+$)/g, "");

  document.getElementById("userInput").innerHTML = userInputStr;

  /* Here we give simple implementation for prefix matching */
  if (userInputStr.length == 0){
    document.getElementById("result").innerHTML = "";
    return;
  }

  var arrayName = "words_prefix_" + userInputStr[0];

  var matched_count = 0;
  var matched_array = new Array();
  /* Start to search the matched prefix,
 *      about the use of eval(), try Google Search keyword: javascript evaluate string as variable */
  for ( i=0; i < eval(arrayName).length; i++ ) {
    if (eval(arrayName)[i].indexOf(userInputStr) == 0) {// If the word starts with the string that users input
      matched_array.push(eval(arrayName)[i]);
      matched_count += 1;
    }
    if (matched_count == 25) {break;}//show no more than 25 words in prefix match
  }
  /* compile matched result into HTML code */
  var matched_result = new String();
  for (i=0; i<matched_array.length; i++) {
    matched_result = matched_result + matched_array[i] + "<br />";
  }
  document.getElementById("result").innerHTML = matched_result;// show matched result
}

References:

[1]Google Search Keyword: javascript string prefix match
[2]JavaScript startsWith and endsWith Implementation for Strings
[3]JavaScript String match() Method
[4]The Most Efficient Algorithm to Find First Prefix-Match From a Sorted String Array? - Stack Overflow
Powered by Github Pages, Pelican, pyScss.