Determine if a string is a sequence of dictionary words

Question

This is Leetcode problem 139: "Wordbreak"

Problem: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.

Example:

• Input: s = "applepenapple", wordDict = ["apple", "pen"]
• Output: true

---

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word. my solution

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        """


        """

        def prune(i):
            if i == len(s):
                return True
            elif  i >len(s):
                return False
            else:
                for word in wordDict:
                    m = len(word)
                    if s[i:i+m] == word and prune(i+m):
                        return True

                return False
        wordDict.sort(key = lambda x:-len(x))
        return prune(0)

I believe the time complexity for my solution to be O(m^n), where m is the amount of words in wordDict and n is the length of the string s. Space wise is just the recursion stack so O(n). I'm having a hard time figuring out how to optimize my solution by either using bfs/dfs or dynamic programming. What would I memoize?

Answer 1

"""DocStrings"""

+1 for adding a doc string to the wordBreak() method, but -1 for not having any content in it.

PEP-008

Your code diverges from the PEP-008 guidelines in several areas:

1. Use snake_case for functions and variables, not mixedCase.
2. Use a single space around operators (elif i > len(s):), not 2 spaces, and then no spaces.
3. Add a blank line between the inner prune() function and the outer function, as well as between the class Solution and its first method.

Use pylint or pyflakes or similar to ensure your code follows proper conventions.

Variable Names

Variable names like s are very terse, but since it is given that name in the question, is forgivable.

Variable names like wordDict are misleading, and should be avoided! wordDict is actually a list, not a dict. Although that name was given in the question, you should correct it to word_list, or simply words to avoid confusion. (+1 for the type hint; it helps avoid some confusion. But rename the parameter anyway.)

i is acceptable as a loop index, but there is no obvious loop. idx or pos may improve clarity.

m is unacceptable. It in no way suggests it is the length of a word. Use a more descriptive variable name.

Dead Code

elif i > len(s):
    return False

At what point will this branch every be taken? The only way is if prune(i+m) is called when i+m is greater than len(s). But if m is the length of word, and s[i:i+m] == word is true, it is impossible for i+m to exceed len(s). This branch is dead code, and can be removed.

Algorithmic Improvements

You are sorting your "dictionary" by length, so that you check the longest words first. However, this doesn't actually guarantee any speed improvements. At any step, if the next possible word is the shortest one, you've guaranteed it will be the last one checked. Ditch the sort.

What you want to do is reduce the number of words from the "dictionary" you are testing at each step. One obvious way would be to turn the "dictionary" into an actual dict, say, storing the list of words which start with a given letter:

word_dict = {
              "a": ["apple"],
              "p": ["pen"],
            }

Or more programmatically:

word_dict = defaultdict(list, ((word[:1], word) for word in wordDict))

Then at each step, instead of comparing s[i:i+len(word)] to each and every word in wordDict, you would compare to the list of words in word_dict[s[i:i+1]], which should be significantly smaller.

This method will degenerate if all the dictionary words start with the same letter (["aaaa", "aaab", "aaac", "aaad"]), but you could handle this by storing the dictionary as a tree structure instead.

Another alternative would be to separate wordDict into sets of words of different lengths:

words_by_length = { 3: { "pen" }, 5: { "apple" } }

Then, at each stage, you could do a single set containment test for each word length:

for word_length, word_list in words_by_length.items():
    if s[i:i+word_length] in words_list:
        # ...

Answer 2

This task can be accomplished using a regular expression.

As an example, for the input wordDict = ["apple", "pen"], one can build a regular expression
r"(apple|pen)+", and then match it against the entire input string "applepenapple" (use re.fullmatch, not re.match). The underlying algorithm for regular expression matching is based on a finite automata and is very efficient.