Try a trie implementation :)

trie.py

class TrieNode(object):

    def __init__(self, alphabet_size=26):
        self.value = 0
        self.alpha_size = alphabet_size
        self.children = [None for _ in range(self.alpha_size)]
        
    def leaf(self):
        return self.value != 0

    def free(self):
        for node in self.children:
            if node:
                return False
        return True

class Trie(object):

    def __init__(self, root=None):
        self.root = root if root else TrieNode()
        self.count = 0

    def _getindex(self, keychar):
        ind = ord(keychar) - ord('a')
        if ind < 0 or ind >= self.root.alpha_size:
            raise Exception('invalid index {ind}'.format(ind))
        return ind

    def insert(self, key):
        length = len(key)
        crawl = self.root
        self.count += 1 
        for level in range(length):
            ind = self._getindex(key[level])
            if crawl.children[ind]:
                crawl = crawl.children[ind]
            else:
                crawl.children[ind] = TrieNode()
                crawl = crawl.children[ind]

        crawl.value = self.count

    def search(self, key):
        length = len(key)
        crawl = self.root

        for level in range(length):
            ind = self._getindex(key[level])
            if not crawl.children[ind]:
                return False
            else:
                crawl = crawl.children[ind]

        return (crawl and crawl.value!=0)

    def _delhelper(self, node, key, level, length):
        if node:
            if level == length:
                if node.value > 0:
                    node.value = 0
                    if node.free():
                        return True
                else:
                    return False
            else:
                ind = self._getindex(key[level])
                if(self._delhelper(node.children[ind], key, level+1, length)):
                    node.children[ind] = None
                    return (not node.leaf() and node.free())
                else:
                    return False

        return False

    def delete(self, key):
        if key:
            self._delhelper(self.root, key, 0, len(key))


if __name__ == '__main__':

    strings = ["she", "sells", "sea", "shore", "the", "by", "sheer"]
    trie = Trie()
    for string in strings:
        trie.insert(string)

    print "she", trie.search("she")
    print "sho", trie.search("sho")
    print "shores", trie.search("shores")
    print "shore", trie.search("shore")

    print 
    print "Deleted she ", trie.delete("she")
    print 
    
    print "she", trie.search("she")
    print "sho", trie.search("sho")
    print "shores", trie.search("shores")
    print "shore", trie.search("shore")