Word Break- DSA Tutorial Class

Determine whether an input string can be divided into a space-separated sequence of dictionary terms given a dictionary of words. For further information, see the examples that follow.
This is a well-known Google interview question that is being asked by many other businesses as well.

Consider the following dictionary 
{ i, like, sam, sung, samsung, mobile, ice, 
 cream, icecream, man, go, mango}

Input: ilike
Output: Yes 
The string can be segmented as “i like”.

Input: ilikesamsung
Output: Yes
The string can be segmented as “i like samsung” 
or “i like sam sung”.

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Function to check if the given string can be broken
// down into words from the word list
bool WordBreak(const string& str, const vector<string>& d)
{
    // If the string is empty, it can be broken down into
    // an empty list of words
    if (str.empty())
        return true;

    int n = str.length();

    // Try every prefix of length i 
    for (int i = 1; i <= n; ++i) {
        
        // if the prefix of length i is a dictionary word
        // and rest of the string can also be broken into
        // valid words, return true
        string prefix = str.substr(0, i);
        if (find(d.begin(), d.end(), prefix) != d.end() && 
            WordBreak(str.substr(i), d)) {
            return true;
        }
    }

    return false;
}

int main()
{
    vector<string> d = { "mobile", "samsung",  "sam",  "sung", "man",
                         "mango",  "icecream", "and",  "go",   "i",
                         "like",   "ice",      "cream" };
    
    cout << (WordBreak("ilikesamsung", d) ? "Yes\n" : "No\n");
    cout << (WordBreak("iiiiiiii", d) ? "Yes\n" : "No\n");
    cout << (WordBreak("", d) ? "Yes\n" : "No\n");
    cout << (WordBreak("ilikelikeimangoiii", d) ? "Yes\n" : "No\n");
    cout << (WordBreak("samsungandmango", d) ? "Yes\n" : "No\n");
    cout << (WordBreak("samsungandmangok", d) ? "Yes\n" : "No\n");

    return 0;
}

Java

import java.util.*;

public class Main {
    // Function to check if the given word can be broken
    // down into words from the wordList
    static boolean wordBreak(List<String> wordList,
                             String word)
    {
        // If the word is empty, it can be broken down into
        // an empty list of words
        if (word.isEmpty()) {
            return true;
        }

        int wordLen = word.length();

        // Check if the word can be broken down into
        // words from the wordList
        for (int i = 1; i <= wordLen; ++i) {
            String prefix = word.substring(0, i);

            if (wordList.contains(prefix)
                && wordBreak(wordList, word.substring(i))) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args)
    {
        List<String> wordList = Arrays.asList(
            "mobile", "samsung", "sam", "sung", "man",
            "mango", "icecream", "and", "go", "i", "like",
            "ice", "cream");

        boolean result
            = wordBreak(wordList, "ilikesamsung");

        System.out.println(result); // Output: true
    }
}

Python

# Function to check if the given word can be broken
# down into words from the wordList
def wordBreak(wordList, word):
    # If the word is empty, it can be broken down into
    # an empty list of words
    if not word:
        return True
    
    wordLen = len(word)
    
    # Check if the word can be broken down into
    # words from the wordList
    for i in range(1, wordLen + 1):
        prefix = word[:i]
        
        if prefix in wordList and wordBreak(wordList, word[i:]):
            return True
    
    return False

wordList = ["mobile", "samsung", "sam", "sung", "man",
                "mango", "icecream", "and", "go", "i",
                "like", "ice", "cream"]
    
result = wordBreak(wordList, "ilikesamsung")
    
print(result)

JS

// Function to check if the given word can be broken down into words from the wordList
function wordBreak(wordList, word) {
    // If the word is empty, it can be broken down into an empty list of words
    if (word === '') {
        return true;
    }

    const wordLen = word.length;

    // Check if the word can be broken down into words from the wordList
    for (let i = 1; i <= wordLen; i++) {
        const prefix = word.substr(0, i);

        if (wordList.includes(prefix) && wordBreak(wordList, word.substr(i))) {
            return true;
        }
    }

    return false;
}

// Main function
function main() {
    const wordList = [
        "mobile", "samsung", "sam", "sung", "man",
        "mango", "icecream", "and", "go", "i",
        "like", "ice", "cream"
    ];

    const result = wordBreak(wordList, "ilikesamsung");

    console.log(result); // Output: true
}

// Call the main function
main();

Output

Yes
Yes
Yes
Yes
Yes
No