Leet Code 139. Word Break

https://leetcode.com/problems/word-break/

Example 1:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Iss wale eg. me 9th index pr False reh jaega, because "og" word nhi mila humein dictionary me,

hence, will return FALSE.

package pep.Day83;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class LeetCode_139_Word_Break {

    public static void main(String[] args) {
        String s = "applepenapple";
        List<String> wordDict = Arrays.asList("apple", "pen");

        System.out.println(wordBreak(s, wordDict));
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>();
        int maxLen = 0;

        for (String ss : wordDict) {
            set.add(ss);
            maxLen = Math.max(maxLen, ss.length());
        }

        int n = s.length();
        boolean[] dp = new boolean[n + 1];

        // yha tak ka word present hai, yha se check krna start kr do
        dp[0] = true;
        for (int i = 0; i <= n; i++) {
            if (dp[i] == true) {
                for (int l = 1; l <= maxLen && i + l <= n; l++) {
                    String sb = s.substring(i, i + l);
                    if (set.contains(sb)) {
                        dp[i + l] = true;
                    }

                }
            }
        }
        // LAST INDEX PR TRUE HOGA TO SAB WORD MIL JAENGE
        return dp[n];
    }
}