P#11 String Auto Complete System (문자열 자동완성기능 구현)

All problems are from https://www.dailycodingproblem.com/

전문가의 말을 믿기보다는 내가 전문가가 될 것. - 존 리 

Be an Expert whether than believing an Expert. - John Lee

Solution Codes : https://github.com/Kusin/DailyCoding

Kusin/DailyCoding

 

Daily Coding Problem#11 : String Auto Complete System (문자열 자동완성 시스템 구현)

Problem Description

Solution#1

Idea

The hint nails it. It implies a data structure "Trie". 

Which is called as "Prefix Tree"

 

You can study it from Leetcode.

https://leetcode.com/problems/implement-trie-prefix-tree/solution/

Personally, I enjoyed this youtube video explaining implementation of Trie.

 

After mastering Trie, you would easily feel that it's not the end.

Our main goal is to implement the auto complete system.

Since we already know how to code 'startswith(prefix)' method, we can figure it whether if a string exists that contain the given prefix. Let's go further.

 

After Determining the existence, we have to fin the exact strings. How should we do? 

Let's make a method that returns list of strings that could be made of the given node. The starting node is the node after the loop. If we implement the method with dfs, the returned list would be the suffix that can be attacthed to the given prefix. So we can simply attach the prefix to each elements of the suffix list and return it.

 

Implementation

Solution#2

Idea

Note that the strings are already given. We have to preprocess it. And queries to conduct are some sort of 'Searching'. Hmm, preprocess and queries. What do you think of? It's a similiar situation with

'Binary Search'. How would it be, if we can sort strings and process a binary search? It would be fast. let n number of strings, and m max length of a string. 

Then preprocessing takes O(nm log n) and single search takes O(m log n). Quite fast, :D.

 

How should we search it? Suppose we search strings that contain prefix "Penta". 

First, find the lower bound of it. Now we have strings that is latter than "Penta".

ex) "Penta" , "Pentaa" , "Pentak" , "Pentb" ,"Zico", ...

Note that words "Pentb" and latter are not the strings that we are fining.

Second, Modify the string and find the lower bound of the modified string. 

Change the last character. Increase it by 1. (in ASCII Code)

Third let the lowerbounds at previous steps L1,L2. 

L1 ~ L2-1 are the strings we are finding.

 

I'll implement it by using bisect method.

 

Check out https://docs.python.org/3.9/library/bisect.html

 

Implementation