educative.io

Https://www.educative.io/courses/algorithms-ds-interview

Courses
,
#1

What is the meaning of this line

ok = ok || dfs(i + word.length(), memo, s, words);

boolean ok = false;

    for (String word : words) {

        if (s.substring(i).startsWith(word)) {

            ok = ok|| dfs(i + word.length(), memo, s, words);

        }

    }
Summary

This text will be hidden

#2

Hi @Vincent_Mwagiru!

In the first line, ok is a boolen variable whose initial value has been set to false.

So the following line: ok = ok || dfs(i + word.length(), memo, s, words); is resetting the value of ok to true or false based on the result of dfs() function.

The dfs function will return false untill no match will be met and since ok is initially false too, so this will evaluate to false || false which, in turn, will be false as well meaning match not found.

When dfs, however, returns true, it evaluates to false || true and therefore, ok becomes true and the function moves ahead.

I hope it helps!

1 Like
#3

This answer has really helped me understand the problem. I’ll go back and have a look at the problem again. Thanks @Ramez_Salman

#4

Hi @Ramez_Salman ,
I refactored the solution a bit and wrote it as below:

import java.util.Arrays;
class Solution {
public static boolean wordBreak(String s, String[] words) {
// WRITE YOUR BRILLIANT CODE HERE
return dfs(s, words, 0, new Boolean[s.length()]);
}

public static boolean dfs(String s, String[] words, int index, Boolean[] visited){
    if (index == s.length()) return true;
    
    if(visited[index] != null) return visited[index];
    boolean res = false;
    for(String word : words){
        if(s.substring(index).startsWith(word)){
            res = dfs(s, words, index + word.length(), visited); //return true only if word is part of substring 
        }
    }
    visited[index] =  res ;
    return visited[index];

}

}

//res = dfs(s, words, index + word.length(), visited); //return true only if word is part of substring
this is what i changed . it passed all the test cases …am just wondering if that statement instead of
res = res || dfs(s, words, index + word.length(), visited) has any change in terms of accuracy.

#5

Hi @Vincent_Mwagiru!

I don’t think there should be any change in terms of accuracy. Essentially, you’re doing the same thing as the previous solution.

1 Like