Word Break (Memoization)

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Word Break, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = {}

def search(words, s):
  if s == '': return True

  global cache
  if s not in cache:
    cache[s] = False

    for i in range(len(s) - 1, -1, -1):
      if s[0:i + 1] in words:          
        cache[s] = search(words, s[i + 1:])

  return cache[s]

words = ['i', 'like', 'sam', 'sung', 'samsung', 'mobile', 'ice', 'cream', 'icecream', 'man', 'go', 'mango']
string = 'ilikesamsung'

print(search(words, string))

const cache = {}

function search(words, s) {
  if (s === '') return true;

  if (cache[s] === undefined) {
    cache[s] = false;

    for (let i = s.length - 1; i >= 0; i--) {
      if (words.indexOf(s.slice(0, i + 1)) >= 0) {          
        cache[s] = search(words, s.slice(i + 1));
      }
    }
  }

  return cache[s];
}

const words = ['i', 'like', 'sam', 'sung', 'samsung', 'mobile', 'ice', 'cream', 'icecream', 'man', 'go', 'mango'];
const string = 'ilikesamsung';

console.log(search(words, string));