python given query string find a set of strings with same beginning

Question

Edit: I appreciate all the answers but could anyone tell me why my solution is not working? I wanted to try to do this without the .startswith() thank you!

I am trying to complete this excercise:

Implement an autocomplete system. That is, given a query string and a set of all possible query strings, return all strings in the set that have s as a prefix. For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal]. Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries.

But I get a empty list. What could I be doing wrong? I thought this would give me [deer, deal]

def autocomplete(string,set):
    string_letters = []
    letter_counter = 0
    list_to_return = []

    for letter in string:
        string_letters.append(letter)

    for words in set:
        for letter in words:
            if letter_counter == len(string):
                list_to_return.append(words)
            if letter == string_letters[letter_counter]:
                letter_counter += 1
            else:
                break
    return list_to_return

print(autocomplete("de", ["dog","deer","deal"]))

output:

[]

Edit: I appreciate all the answers but could anyone tell me why my solution is not working? I wanted to try to do this without the .startswith() thank you!

Per your edit, I have provided an explanation as to why your code did not work as intended in my answer. — James Powis
– James Powis, Commented Jul 6, 2020 at 22:53

James Powis · Accepted Answer · 2020-07-06 22:52:31Z

Here is how I would accomplish what you are trying to do:

import re
strings = ['dog', 'deer', 'deal']
search = 'de'
pattern = re.compile('^' + search)
[x for x in strings if pattern.match(x)]

RESULT: ['deer', 'deal']

However in most cases with a use case such as this, you might want to ignore the case of the search string and search field.

import re
strings = ['dog', 'Deer', 'deal']
search = 'De'
pattern = re.compile('^' + search, re.IGNORECASE)
[x for x in strings if pattern.match(x)]

RESULT: ['Deer', 'deal']

To answer the part of why your code does not work, it helps to add some verbosity to the code:

def autocomplete(string,set):
    string_letters = []
    letter_counter = 0
    list_to_return = []

    for letter in string:
        string_letters.append(letter)

    for word in set:
        print(word)

        for letter in word:
            print(letter, letter_counter, len(string))
            if letter_counter == len(string):
                list_to_return.append(word)
            if letter == string_letters[letter_counter]:
                letter_counter += 1
            else:
                print('hit break')
                break
    return list_to_return

print(autocomplete("de", ["dog","deer","deal"]))

Output:

dog
('d', 0, 2)
('o', 1, 2)
hit break
deer
('d', 1, 2)
hit break
deal
('d', 1, 2)
hit break
[]

As you can see in the output for dog 'd matched but o did not', this made the letter_counter 1, then upon deer 'd != 'e' so it breaks... This perpetuates over and over. Interestingly setting 'ddeer' would actually match due this behavior. To fix this you need to reset the letter_counter in the for loop, and have additional break points to prevent over-reving your indexes.

def autocomplete(string,set):
    string_letters = []
    list_to_return = []

    for letter in string:
        string_letters.append(letter)

    for word in set:
        # Reset letter_counter as it is only relevant to this word.
        letter_counter = 0
        print(word)

        for letter in word:
            print(letter, letter_counter, len(string))
            if letter == string_letters[letter_counter]:
                letter_counter += 1
            else:
                # We did not match break early
                break
            if letter_counter == len(string):
                # We matched for all letters append and break.
                list_to_return.append(word)
                break
    return list_to_return

print(autocomplete("de", ["dog","deer","deal"]))

Red · Accepted Answer · 2020-07-06 21:24:43Z

0

I notice the hint, but it's not stated as a requirement, so:

def autocomplete(string,set):
    return [s for s in set if s.startswith(string)]

print(autocomplete("de", ["dog","deer","deal"]))

str.startswith(n) will return a boolean value, True if the str starts with n, otherwise, False.

answered Jul 6, 2020 at 21:24

Red

27.7k8 gold badges44 silver badges63 bronze badges

Comments

Murgalha · Accepted Answer · 2020-07-06 21:24:47Z

0

You can just use the startswith string function and avoid all those counters, like this:

def autocomplete(string, set):
    list_to_return = []

    for word in set:
        if word.startswith(string):
            list_to_return.append(word)
    return list_to_return

print(autocomplete("de", ["dog","deer","deal"]))

answered Jul 6, 2020 at 21:24

Murgalha

3783 silver badges8 bronze badges

Comments

nagyl · Accepted Answer · 2020-07-06 21:26:34Z

0

Simplify.

def autocomplete(string, set):
    back = []
    for elem in set:
        if elem.startswith(string[0]):
            back.append(elem)
    return back

print(autocomplete("de", ["dog","deer","deal","not","this","one","dasd"]))

answered Jul 6, 2020 at 21:26

nagyl

1,6641 gold badge9 silver badges18 bronze badges

Collectives™ on Stack Overflow

python given query string find a set of strings with same beginning

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related