Untitled

import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict); // Use a set for O(1) lookups
        return canBreak(s, 0, wordSet, new Boolean[s.length()]);
    }

    private boolean canBreak(String s, int start, Set<String> wordSet, Boolean[] memo) {
        // Base case: If we've checked the entire string, return true.
        if (start == s.length()) return true;

        // Check memoized results.
        if (memo[start] != null) return memo[start];

        // Try all substrings starting from 'start'.
        for (int end = start + 1; end <= s.length(); end++) {
            String prefix = s.substring(start, end);
            // If the prefix exists in the dictionary and the rest of the string can be segmented.
            if (wordSet.contains(prefix) && canBreak(s, end, wordSet, memo)) {
                return memo[start] = true;
            }
        }

        // If no valid segmentation found, memoize and return false.
        return memo[start] = false;
    }
}