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

Building upon understanding of Word Break (Memoization). Pay attention to the cache. Tabulation essentially reconstructs the cache.

Start with the foundation – the base cases, which are the simplest solutions. Then, layer by layer, use the results of the previous layers to calculate the solutions for the next level. This way, we systematically build up the entire solution, avoiding redundant calculations and ensuring efficiency. It is like building a pyramid.

The underlying calculation logic remains fundamentally identical to the original recursive approach, albeit executed in reverse order.

# Python implementation

def search(words, s):
  cache = [False for _ in range(len(s) + 1)]
  cache[0] = True

  for i in range(len(s) + 1):
    for j in range(i):
      if cache[j] and s[j:i] in words:
        cache[i] = True
        break
  
  return cache[len(s)]

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

print(search(words, string))

// Javascript implementation

function search(words, s) {
  const cache = Array(s.length + 1).fill(false);
  cache[0] = true;

  for (let i = 0; i < s.length + 1; i++) {
    for (let j = 0; j < i; j++) {
      if (cache[j] && words.includes(s.slice(j, i))) {
        cache[i] = true;
        break;
      }
    }
  }
  
  return cache[s.length];
}

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

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

Word Break (Tabulation)

Hint