HomeLeetcode139. Word Break - Leetcode Solutions
Leetcode

139. Word Break – Leetcode Solutions

Declan Clarke

Description

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

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Examples:

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".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Solution in Python

To solve the problem of determining if a string s can be segmented into a space-separated sequence of one or more dictionary words from wordDict, we can use a dynamic programming approach.

Approach

  1. Dynamic Programming Setup:
    • We’ll use a boolean array dp where dp[i] will be True if the substring s[0:i] can be segmented into words in wordDict.
    • Initialize dp[0] to True because an empty string can be segmented trivially.
  2. Transition:
    • Iterate over each character in the string s from 1 to len(s).
    • For each position i, check every possible word in wordDict.
    • If a word matches the substring ending at position i and the substring before the matched word can be segmented (dp[i - len(word)] is True), then set dp[i] to True.
  3. Final Result:
    • The final answer will be in dp[len(s)], indicating whether the entire string can be segmented into dictionary words.
Python
from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # Convert the word dictionary to a set for O(1) lookup time
        word_set = set(wordDict)
        
        # dp[i] is True if s[:i] can be segmented into words in wordDict
        dp = [False] * (len(s) + 1)
        dp[0] = True  # Base case: empty string
        
        # Iterate over the length of the string
        for i in range(1, len(s) + 1):
            # Check each word in the dictionary
            for word in word_set:
                # If the current position i is greater than or equal to the word length
                # and the substring s[i-len(word):i] matches the word
                # and the substring before the matched word can be segmented
                if i >= len(word) and s[i - len(word):i] == word and dp[i - len(word)]:
                    dp[i] = True
                    break
        
        # The result is whether the entire string can be segmented
        return dp[len(s)]

Detailed Explanation of the Code

  1. Initialization:
    • word_set = set(wordDict): Convert the word dictionary to a set for fast lookups.
    • dp = [False] * (len(s) + 1): Create a DP array of size len(s) + 1 initialized to False.
    • dp[0] = True: The base case where an empty string is always considered as segmented.
  2. Iterate Over the String:
    • For each index i from 1 to len(s), check if s[0:i] can be segmented.
    • For each word in the word dictionary:
      • Check if the current substring s[i - len(word):i] matches the word.
      • Check if the substring before this word can be segmented (dp[i - len(word)]).
  3. Update DP Array:
    • If both conditions are met, set dp[i] to True and break out of the inner loop because we found a valid segmentation for s[0:i].
  4. Return the Result:
    • The value dp[len(s)] will tell if the entire string s can be segmented into words from the dictionary.

Solution in Javascript

JavaScript
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    // Convert the word dictionary to a set for O(1) lookup time
    let wordSet = new Set(wordDict);
    
    // dp[i] is true if s.slice(0, i) can be segmented into words in wordDict
    let dp = new Array(s.length + 1).fill(false);
    dp[0] = true;  // Base case: empty string
    
    // Iterate over the length of the string
    for (let i = 1; i <= s.length; i++) {
        // Check each word in the dictionary
        for (let word of wordSet) {
            let wordLen = word.length;
            // If the current position i is greater than or equal to the word length
            // and the substring s.slice(i - wordLen, i) matches the word
            // and the substring before the matched word can be segmented
            if (i >= wordLen && s.slice(i - wordLen, i) === word && dp[i - wordLen]) {
                dp[i] = true;
                break;
            }
        }
    }
    
    // The result is whether the entire string can be segmented
    return dp[s.length];
};

Solution in Java

Java
import java.util.List;
import java.util.Set;
import java.util.HashSet;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // Convert the word dictionary to a set for O(1) lookup time
        Set<String> wordSet = new HashSet<>(wordDict);
        
        // dp[i] is true if s.substring(0, i) can be segmented into words in wordDict
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;  // Base case: empty string
        
        // Iterate over the length of the string
        for (int i = 1; i <= s.length(); i++) {
            // Check each word in the dictionary
            for (String word : wordSet) {
                int wordLen = word.length();
                // If the current position i is greater than or equal to the word length
                // and the substring s.substring(i - wordLen, i) matches the word
                // and the substring before the matched word can be segmented
                if (i >= wordLen && s.substring(i - wordLen, i).equals(word) && dp[i - wordLen]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        // The result is whether the entire string can be segmented
        return dp[s.length()];
    }
}

Solution in C#

C#
using System.Collections.Generic;

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        // Convert the word dictionary to a HashSet for O(1) lookup time
        HashSet<string> wordSet = new HashSet<string>(wordDict);
        
        // dp[i] is true if s.Substring(0, i) can be segmented into words in wordDict
        bool[] dp = new bool[s.Length + 1];
        dp[0] = true;  // Base case: empty string
        
        // Iterate over the length of the string
        for (int i = 1; i <= s.Length; i++) {
            // Check each word in the dictionary
            foreach (string word in wordSet) {
                int wordLen = word.Length;
                // If the current position i is greater than or equal to the word length
                // and the substring s.Substring(i - wordLen, wordLen) matches the word
                // and the substring before the matched word can be segmented
                if (i >= wordLen && s.Substring(i - wordLen, wordLen) == word && dp[i - wordLen]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        // The result is whether the entire string can be segmented
        return dp[s.Length];
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com