Search a list of string with a given substring in python

Question

I'm developing a dictionary kind of application using python. In my code, there is a list which consists of sorted set of strings. when a user give some text, I want to get all the string starting with the given string. In other words, I just want to suggest words while user is typing.

Example : If user typed the word "sub", I want to take all the string from the list starting with the substring "sub".

Can anyone give me an algorithm to do this? Thanks all.

this features is usually referred to as auto-complete; however, if you query an Internet search engine for "python and "auto-complete", most of the results will relate to auto-complete python syntax for text editors. — doug
– doug, Commented Mar 20, 2012 at 19:45
Consider Huffman coding as food for thought on this problem: en.wikipedia.org/wiki/Huffman_coding — wberry
– wberry, Commented Mar 20, 2012 at 22:12

Colin · Accepted Answer · 2012-03-20 19:54:43Z

1

Depending on the size of the list, you could just iterate through it and use the startswith() string function to get the result. If that's too slow, a common way is to use a prefix tree.

answered Mar 20, 2012 at 19:54

Colin

10.9k11 gold badges51 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

kasavbere · Accepted Answer · 2012-03-21 00:29:49Z

0

What you need is a trie data structure, which is perfect for what you seek. Your code needs to handle heavy read/retrieval. Look up trie. if you need implementation let me know.

answered Mar 21, 2012 at 0:29

kasavbere

6,02314 gold badges52 silver badges73 bronze badges

Collectives™ on Stack Overflow

Search a list of string with a given substring in python

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related