Word Break medium

Problem Statement

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

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".

Steps

1. Initialization: Create a boolean array dp of size s.Length + 1. dp[i] will be true if the substring s[0...i-1] can be segmented into words from wordDict, and false otherwise. Initialize dp[0] to true (empty substring is always valid).

2. Iteration: Iterate through the string s from index 1 to s.Length. For each index i, check if the substring s[j...i-1] (where j ranges from 0 to i-1) is in wordDict.

3. Dynamic Programming: If s[j...i-1] is in wordDict and dp[j] is true (meaning the substring s[0...j-1] can be segmented), then set dp[i] to true. This means that the substring s[0...i-1] can be segmented.

4. Result: After iterating through the entire string, dp[s.Length] will indicate whether the entire string s can be segmented. Return dp[s.Length].

Explanation

This solution uses dynamic programming to efficiently solve the problem. The dp array stores the results of subproblems. Instead of recursively checking all possible segmentations (which would lead to exponential time complexity), we build up the solution from smaller subproblems to larger ones. Each dp[i] only needs to be calculated once, making the overall algorithm much faster. The check for whether a substring is in wordDict can be optimized using a HashSet for O(1) lookup time.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public 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];
    }
}

Complexity

• Time Complexity: O(n^2), where n is the length of the string s. The nested loops iterate through all possible substrings. The HashSet lookup is O(1).
• Space Complexity: O(n), due to the dp array. The HashSet uses space proportional to the size of wordDict.