Word Break In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement: Word Break

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

Note:

• You may assume that the dictionary does not contain any duplicate words.

Example

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Explanation: Return false because “catsandog” cannot be segmented into words from the dictionary.

Approach and Algorithm

1. Dynamic Programming Approach:
   • We use a DP array dp[i], where dp[i] is True if the substring s[0...i] can be segmented into words from the dictionary.
   • Initially, dp[0] is True because an empty string is trivially segmentable.
   • For each i from 1 to n (length of string s), check all possible j such that dp[j] is True and the substring s[j...i] exists in the dictionary.
   • If both conditions are true, set dp[i] = True.
2. Time Complexity:
   • The outer loop runs O(n) times, where n is the length of string s.
   • The inner loop checks all substrings s[j...i], so the time complexity is approximately O(n^2).
3. Space Complexity:
   • The space complexity is O(n) due to the dp[] array.

Code in Multiple Languages

C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool wordBreak(char* s, char** wordDict, int wordDictSize) {
    int n = strlen(s);
    bool dp[n + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < wordDictSize; j++) {
            int len = strlen(wordDict[j]);
            if (i >= len && dp[i - len] && strncmp(s + i - len, wordDict[j], len) == 0) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

int main() {
    char* wordDict[] = {"leet", "code"};
    int wordDictSize = sizeof(wordDict) / sizeof(wordDict[0]);
    char s[] = "leetcode";
    printf("%d\n", wordBreak(s, wordDict, wordDictSize));  // Output: 1 (true)
    return 0;
}

C++

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

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

int main() {
    vector<string> wordDict = {"leet", "code"};
    string s = "leetcode";
    cout << wordBreak(s, wordDict) << endl;  // Output: 1 (true)
    return 0;
}

Java

import java.util.*;

public class WordBreak {
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        List<String> wordDict = Arrays.asList("leet", "code");
        String s = "leetcode";
        System.out.println(wordBreak(s, wordDict));  // Output: true
    }
}

Python

def wordBreak(s: str, wordDict: list) -> bool:
    wordSet = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break

    return dp[n]

# Example
s = "leetcode"
wordDict = ["leet", "code"]
print(wordBreak(s, wordDict))  # Output: True

C#

using System;
using System.Collections.Generic;

public class WordBreak {
    public static bool WordBreak(string s, IList<string> wordDict) {
        HashSet<string> wordSet = new HashSet<string>(wordDict);
        int n = s.Length;
        bool[] dp = new bool[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.Contains(s.Substring(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }

    public static void Main() {
        List<string> wordDict = new List<string> { "leet", "code" };
        string s = "leetcode";
        Console.WriteLine(WordBreak(s, wordDict));  // Output: True
    }
}

JavaScript

function wordBreak(s, wordDict) {
    const wordSet = new Set(wordDict);
    const n = s.length;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordSet.has(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

console.log(wordBreak("leetcode", ["leet", "code"]));  // Output: true

---

Summary

• Time Complexity: O(n^2), where n is the length of the string s. The outer loop runs n times, and the inner loop checks all substrings.
• Space Complexity: O(n), where n is the length of the string s due to the dp[] array.
• Algorithm: Use dynamic programming to check whether substrings of s can be formed from the dictionary words.