Question

In C++, given an array of strings(assume the array is sorted lexicographically), and an input prefix, how would I return all the words that start with the given prefix. (must use binary search for searching)

For example, given the following array, if user were to input, "Can" our output would be

Words that start with "can" are :

Candy Bars

       Candy Buttons

       Candy Melts

       Candy Props

       Candy Sprinkles

       Candy Sticks

       Candy Straws

       Candy Toys


----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

This is the array of strings

Bite Size

       Bon Bons

       Brittle Candy

       Bubble Gum

       Candy Bars

       Candy Buttons

       Candy Melts

       Candy Props

       Candy Sprinkles

       Candy Sticks

       Candy Straws

       Candy Toys

       Caramels

       CBD Candy

       Chewy Candy

       Chewing Gum

       Chocolates

       Circus Peanuts Candy

       Classic Candy

       Cotton Candy

       Discontinued Candy

       DIY Candy Kits

       Fruit Drops

       Fruit Pastilles

       Fun Size Candy

       Giant & Big Candy

       Ginger Bites

       Gumballs

       Gumdrops

       Gummy

       Hard Candy

       Jawbreaker Candy

       Jelly Beans

       Jelly Candy

       Jordan Almonds

       Kosher Candy

       Licorices

       Liquid & Spray Candy

       Lollipops & Suckers

       Malt Balls

       Marshmallows

       Mini & Small Candy

       Mints

       Movie Theater Candy

       Nonpareil Candy

       Nostalgic Candy

       Nougat

       Novelty Candy

       Office Candy

       Organic Candy


Answer 1

Solution:

• Binary Search: In this approach, idea is to first compare the given prefix with the middle element of the given array of words:
  • If prefix matches, then return the current array index
  • if prefix is lexicograpgically smaller, look for prefix in first half of array
  • else look for prefix in second half of array

• For debugging purposes, I have hardcoded the input string and prefix, change it accordingly.

C++ code for the above problem:

#include<bits/stdc++.h> 
using namespace std; 

int check(string pre, string word){
    int len_pre = pre.length(), len_word = word.length();
    
    if(len_pre > len_word)
        return 1;
    
    for(int i=0; i<len_pre; i++){
        if(pre[i] < word[i])
            return -1;
        else if(pre[i]>word[i])
            return 1;
    }
    
    return 0;
}  
  
int binarySearch(string str[], string pre, int n) 
{ 
    int l = 0 ; 
    int r = n - 1; 
    while (l <= r)  
    { 
        int m = l + (r - l) / 2;
        
        int res = check(pre, str[m]);
              
        // Check if prefix is present at mid 
        if (res == 0) 
            return m; 

        // If prefix greater, ignore left half of array
        if (res>0) 
            l = m + 1; 

        // If prefix is smaller, ignore right half of array
        else
            r = m - 1; 
    } 
    return -1; 
} 


int main() 
{ 
    string str[] = { "Bite Size", "Bon Bo", "Bubble Gum", "Cand", "Candy", "Candyu", "Candy M", "Candy Mm", "Caram", "Chocola", "Fruit D", "Fruit Drop", "Gum", "Gumball", "Liqu", "practice"}; 
    string pre = "Can"; 
    int n = 16; 
    
    int result = binarySearch(str, pre, n); 

    if (result == -1) 
        cout << ("Prefix not present in the given words")<<endl; 
    else{
        int start = result;
        int end = result;
        
        while(start>=0 && check(pre, str[start]) == 0)
            start--;
        while(end<n && check(pre, str[end]) == 0)
            end++;
        start++;
        end--;
        
        cout<<"Words that start with "<<pre<<" are : "<<endl;
        for(int i=start; i<=end; i++)
            cout<<str[i]<<endl;
    }
} 

Output:

Words that start with Can are : 
Cand
Candy
Candyu
Candy M
Candy Mm