...
/Feature #4: Suggest Possible Queries After Adding White Spaces
Feature #4: Suggest Possible Queries After Adding White Spaces
We'll cover the following...
Description
This feature is an extension of the one we programmed in the previous lesson. Like the last feature, we are given a user query that doesn’t provide a significant number of web hits. Therefore, we have decided to break down the query by adding white spaces to see if valid words can be created by breaking the original query. However, this time the difference is that you are tasked with finding a list of all the possible valid queries created by adding white spaces in the original query.
Let’s suppose the user searches "vegancookbook". This query didn’t get any web hits, so it is sent to the break_query function to check if it’s possible to add white spaces to create valid words. You are also given a dictionary containing all the possible words. In this problem, we will assume that the only possible words are ["an", "book", "car", "cat", "cook", "cookbook", "crash", "cream", "high", "highway", "i", "ice", "icecream", "low", "scream", "veg", "vegan", "way"]. Your function should use this list of strings to determine if the original query can be broken down into words provided in the dictionary. Then, the break_query function should return a list of strings that can be created by breaking down the query into the words present in the dictionary. In the example we just discussed, the function will return ['vegan cook book', 'vegan cookbook', 'veg an cook book', 'veg an cookbook']. Similarly, for the query string "highwaycarcrash" and the same word dictionary, the function should return ["high way car crash", "highway car crash"]
Solution
This problem can also be solved using a dynamic programming (DP) technique. We will be using top-down dynamic programming, which is more efficient, even though other variations of DP can also be used. Let’s take a look at the intuition behind this solution.
Consider the query string, denoted by , "vegancookbook". We will define the result breaking this query into valid words as ...
Create a free account to view this lesson.
By signing up, you agree to Educative's Terms of Service and Privacy Policy