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

The algorithm iterates through the target string, creating substrings by successively removing characters from the end. At each step, it checks if the current substring exists within the given list of words. If the substring is found in the word list, it recursively checks if the remaining portion of the target string (after the found substring) can also be formed using the same word list. If both conditions are met (substring found and remaining portion can be formed), the algorithm returns true.

# Python implementation

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

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

  return False

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) {
  if (s === '') return true;

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

  return false;
}

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

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

Word Break

Hint