The below code works fine for attached input.

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return wordBreakMemo(s, new HashSet<>(wordDict), 0, new Boolean[s.length()]);
    }

    private boolean wordBreakMemo(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)) && wordBreakMemo(s, wordDict, end, memo)) {
                return memo[start] = true;
            }
        }
        return memo[start] = false;
    }
}

But when I change the local variables to global as below, my code take longer to execute, resulting in 'Time Limit Exceeded' on LeetCode.

class Solution {
    HashSet<String> set;
    String s;
    Boolean dp[];
    public boolean wordBreak(String s, List<String> wordDict) {
        
        set=new HashSet();
        set.addAll(wordDict);
        this.s=s;
        dp=new Boolean[s.length()];
        return wordMemo(0);
    }
    public boolean wordMemo(int start)
    {
        if(start==s.length())
            return true;
        
        if(dp[start]!=null)
            return dp[start];
        
        for(int i=start 1; i<=s.length(); i  )
        {
            if(set.contains(s.substring(start, i)) && wordMemo(i))
            {
                dp[start]=true;
                return true;
            }
        }
        return false;
    }
}

Input:

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

Can someone please explain what is happening around here?

CodePudding user response：

Global variables don't have slower fetch times, no.

Whenever you get Time Limit Exceeded in a coding challenge you should assume you have a a flawed or buggy algorithm or data structure. It's never micro factors like fetch times or access modifiers or the language you've chosen. Even if you could speed up your program 10% with better memory access patterns or 100% by switching from Python to C, you're probably off by 10,000% or 10,000,000%, not 100%. That's how bad it can be when your program is accidentally O(n²) or O(2ⁿ) when the challenge designers expect O(n).

Here, the first program has:

return memo[start] = false;

While the second one has just:

return false;

It never memoizes false results. There are a lot more repeated computations, enough to kill the algorithm's Big-O time complexity.