Leet Code 140. Word Break II

package pep.Day83;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class LeetCode_140_Word_Break_2 {

    public static void main(String[] args) {
        String s = "catsanddog";
        List<String> wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");

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

    public static List<String> 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;
                    }

                }
            }
        }

        List<String> ans = new ArrayList<>();
        // koi answer hi nhi mila to return empty List
        if (dp[n] == false)
            return ans;

        // recursion call lagaenge ki mujhe answer laa kr de de
        helper(ans, 0, "", s, set, dp, maxLen);

        return ans;

    }

    public static void helper(List<String> ans, int i, String asf, String s, HashSet<String> set, boolean[] dp, int maxLen) {
        if (i >= s.length()) {
            ans.add(asf.substring(0, asf.length() - 1));
            return;
        }
        for (int l = 1; l <= maxLen && i + l <= s.length(); l++) {
            // agr (0,2) wala substring milta tha to hum 3 index pr TRUE mark krte the
            // hence, hum dp me check krenge
            if (dp[i + l]) {
                String ss = s.substring(i, i + l);
                if (set.contains(ss)) {
                    helper(ans, i + l, asf + ss + " ", s, set, dp, maxLen);
                }
            }

        }

    }
}