Posts Word Break
Post
Cancel

Word Break

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

leetcode

SOLUTION

BRUTE-FORCE (RECURSION) - TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        return wordHelper(s, set, 0);
    }

    public boolean wordHelper(String s, Set<String> set, int idx){

        if(idx == s.length()) return true;

        boolean possible = false;

        for(int i=idx; i<s.length(); i++){

            String substring =  s.substring(idx, i+1);
            if(set.contains(substring)){
                possible = possible || wordHelper(s, set, i+1);
            }

        }

        return possible;

    }

}

TOP-DOWN DYNAMIC PROGRAMMING APPROACH

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {

        Set<String> set = new HashSet<>(wordDict);

        Boolean[] dp = new Boolean[s.length()];
        Arrays.fill(dp, null);

        return wordHelper(s, set, 0, dp);

    }

    public boolean wordHelper(String s, Set<String> set, int idx, Boolean[] dp){

        //if we have processed all the characters, return true
        if(idx == s.length()) return true;

        //default value in Boolean array is null, which means it's not processed already in our case
        //so we calculate its value
        if(dp[idx] == null){

            //init
            boolean possible = false;

            //loop through each index and get the substring from index idx
            //if that substring is present in the dictionary, recursively call wordHelper for rest of the string
            for(int i=idx; i<s.length(); i++){

                String substring =  s.substring(idx, i+1);
                if(set.contains(substring)){
                    possible = possible || wordHelper(s, set, i+1, dp);
                }

            }

            dp[idx] = possible;
        }

        return dp[idx];

    }

}

BOTTOM-DOWN DYNAMIC PROGRAMMING APPROACH

NeetCode YouTube

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {

        int n = s.length();

        // Create a dynamic programming (DP) array of size 'n+1'.
        // dp[i] represents whether the substring from index 'i' to the end of 's' can be segmented into words from 'wordDict'.
        boolean[] dp = new boolean[n + 1];

        // Initialize the last element of 'dp' as true because an empty string can be
        // segmented into words trivially.
        dp[n] = true;

        // Convert 'wordDict' into a HashSet for efficient lookup and remove duplicates if any. (this is not necessary though)
        Set<String> set = new HashSet<>(wordDict);

        // Start iterating through 's' in reverse order (from right to left).
        for (int i = n - 1; i >= 0; i--) {

            // Iterate through each word 'x' in 'wordDict'.
            for (String x : set) {

                int lengthOfWord = x.length();

                // If the length of 'x' is greater than the remaining substring's length,
                // skip this iteration, as it's not possible to match 'x' with the remaining substring.
                if (lengthOfWord > n - i) {
                    continue;
                }

                // Otherwise, check if 'x' is equal to the substring of 's' starting at index 'i' and ending at 'i + length of current word'.
                if (x.equals(s.substring(i, i + lengthOfWord))) {

                    // If 'x' matches the substring, update dp[i] with dp[i + lengthOfWord].
                    // The idea is that if the current word matches the substring, and the rest of the substring starting at i+lengthOfWord the result was true
                    // then we can mark the current state as true
                    dp[i] = dp[i + lengthOfWord];

                    // If dp[i] becomes true, it means we found a valid segmentation,
                    // so we can break out of this inner loop. (if we don't do it, there is a chance that for later words it will change it back to false)
                    if (dp[i] == true) {
                        break;
                    }
                }
            }
        }

        // The final value of dp[0] will indicate whether the entire string 's'
        // can be segmented into words from 'wordDict'.
        return dp[0];
    }
}
This post is licensed under CC BY 4.0 by the author.