Word Break


  • 0

    Click here to see the full article post


  • 0
    L

    Can someone explain the logical OR-ing bit? I don't get what res |= word_Break(s, wordDict, end, memo) does, or how it solves the problem


  • 0

    Logical OR-ing of all results means, we choose every possible valid prefix and check if the remaining portion can form a valid string. If any such prefix exits, we turn the "res" to True. The factor res|=word_Break(...) leads to the "res" in the calling functions to turn to True in such a case.


  • 0

    Puzzled by this statement - "we initialize the element dp[0] as true, since the null string is always present in the dictionary"
    So.. if the empty string is not allowed in wordDict, then dp[0] is false? The DP calculation will change?


  • 0

    @zzhai Yes, the implementation needs to be modified slightly if the empty string isn't allowed.


  • 0

    @vinod23

    Even the empty string isn't allowed, DP[0] can still be initialized as true. DP[0] is for calculating DP[i], 0 < i <= n. DP[0] itself won't get into the result.


  • 0

    @ zzhai If we initialize the dp[0] as True and pass an empty string as the argument, the factor dp[s.length()] (or dp[0]) will return a True, which should not happen for an empty string as per your requirement. Thus, we need to initialize dp[0] as False initially and handle this change appropriately in dp[I] calculations for 0<I<=n. Hope this clears your doubt.


  • 0
    P

    @vinod23 Could you please post a graph for solution #4? That can be of great help to understand the partitioning.


  • 1
    M

    For the fourth solution:

    Wouldn't substring take linear time to calculate therefore making the whole algorithm run in time proportional to n^3?


  • 0
    I

    @lakshay4 -

    We get a true, if there exists a split such that the prefix splits (and an empty suffix) exists in the dictionary.

    if (wordDict.contains(s.substring(start, end))) {
                    res |= word_Break(s, wordDict, end);
    }
    

    i.e., wordDict.Contains() && wordBreak(rest).

    wordBreak() returns true only when we reach end of string. So it just means, all the splits (prefixes) exist in dictionary and i've reached end of string.

    Finally, you could have simply done the real logical-OR which is ||, instead of bitwise-OR, which is what you use |=.
    In either case it will work, because once we find a valid split, res is set to true.


  • 0
    I

    @vinod23 -

    I'm thinking [Logical-OR] res = res || word_Break(s, wordDict, end); works as well as [Bitwise-OR] res = res | word_Break(s, wordDict, end);

    though || stops evaluating further calls to word_break as soon as res becomes true. whereas | will evaluate all calls.

    I'm not sure which you meant to use, because in the text you say "logical-OR", but you've used "bitwise-OR" in code. Not sure which one you intended to use, but i think either operator works here. Can you see if there is a bug if i used || ?


  • 0

    @inswingingyorker Nice idea. I have updated the code. It is better to break the loop when res becomes true.


  • 0

    @inswingingyorker said in Word Break:

    Finally, you could have simply done the real logical-OR which is ||, instead of bitwise-OR, which is what you use |=.

    | is logical there. See Boolean Logical Operators &, ^, and |.

    You mean it's not conditional-or.


    @vinod23 I think it would be cleaner to in approach #1 just do return true instead of using variable res (and return false after the loop) and in approach #2 to use Boolean[] instead of int[] (and use its default null instead of -1).

    Here's one way to do both of these to approach #2 (I also put start == s.length() first and made it return directly, then you don't need length+1 memo entries).

    public class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            return word_Break(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
        }
        public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) {
            if (start == s.length()) {
                return true;
            }
            if (memo[start] != null) {
                return memo[start];
            }
            for (int end = start + 1; end <= s.length(); end++) {
                if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {
                    return memo[start] = true;
                }
            }
            return memo[start] = false;
        }
    }
    

  • 0

    @StefanPochmann Thanks for your suggestions. I have made the changes accordingly.


  • 1

    One more thing: You keep misspelling "memoization" as "memorization".


  • 0

    Sorry corrected.


  • 0

    @vinod23 Two out of four :-P


  • 0
    I

    @StefanPochmann - I was looking at this:
    Logical OR
    and Bitwise OR

    Never mind what it's called. I think we all get the core idea here :)


  • 0
    I

    Sorry for the spam guys, I have one more question if anyone is up for taking it. Here goes:

    To start with, I think I understand the 3 approaches (naive, memoization, tabulation). My question however is this: Does the memoization and tabulation methods use the bool array to represent two entirely different things?

    Reason for my asking is:

    1. tabulation is generally considered as the next step after memoization, where we remove the recursion and fill the table intentionally by iteration.
    2. so, if they were to represent the same things, the table filled by either method should have identical values, although the order in which they are filled would be different. Am I correct here?

    For an example string catdog and a dictionary {cat, dog}

    Tabulation's table looks like [true, false, false, true, false, false, true].
    (What it means?
    true => end pos of string empty, cat, catdog.
    false => end position of other splits that do not form valid words)

    Memoization's cache looks like [true, null, null, true, null, null].
    (What it means? I'm not sure. I guess I don't exactly understand what computation is repeated, for that's what is being cached here. May be i picked a bad example that doesn't show whats repeated but despite that I'm not clear on the repeated computation that we're optimizing).

    @vinod23 @StefanPochmann - I'll be thankful if one of you guys can take a shot at my question and help me understand.


  • 0
    Z

    @mcopes Agree. Any one could prove the complexity is actually N^2?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.