Word Break II

import java.util.* ;
import java.io.*; 
import java.util.ArrayList;

public class Solution {

	public static void solve(String s, ArrayList<String> dictionary, ArrayList<String> ans ,String temp){
		// base case:
		if(s.length() == 0){
			temp.trim();
			ans.add(temp);
			return;
		}

		for( int i = 0; i<s.length(); i++){
			String left = s.substring(0,i+1);
			if(dictionary.contains(left)){
				solve(s.substring(i+1),dictionary,ans ,temp+left+" ");
			}
		}
	}
	public static ArrayList<String> wordBreak(String s, ArrayList<String> dictionary) {
		// Write your code here.
		ArrayList<String> ans = new ArrayList<String>();
		solve(s,dictionary,ans ,"");
		return ans;
	}
}

import java.util.* ;
import java.io.*; 
import java.util.ArrayList;

public class Solution {

	public static ArrayList<String> wordBreak(String s, ArrayList<String> dictionary) {
		// Write your code here.
		Set<String>hs = new HashSet<>(dictionary);
		ArrayList<String>ans = new ArrayList<>();

        solve(s,ans,hs,new ArrayList<>(),0);
		return ans;
	}

	public static void  solve(String s,ArrayList<String> ans , Set<String>hs, ArrayList<String>sub, int start  ){

		if(start == s.length()){
          ans.add(String.join(" ", sub));
		  return ;

		}

		for( int end = start + 1 ;end<=s.length();end++){
			String word = s.substring(start,end);

			if(hs.contains(word)){
				sub.add(word);
                solve(s,ans,hs,sub,end);
				sub.remove(sub.size()-1); // backtracking remove the string 
			}
		}
	}
}

EASY TO UNDERSTAND Using Recursion

and Backtracking 

you just required pen and paper and you are good to go to do this.              

public static ArrayList<String> wordBreak(String s, ArrayList<String> dictionary) {

        // Write your code here.

        ArrayList<String> list= new ArrayList<>();

        solve( s ,dictionary, list, " ");

        return list;

    }

    public static void solve(String s,ArrayList<String> dictionary ,ArrayList<String> list, String ans){

        if(s.length() ==0){

            list.add(ans.trim());

            return;

        }

        for(int i =0;i<s.length();i++){

            String left =s.substring(0,i+1);

            if(dictionary.contains(left)){

            String ros = s.substring(i+1);

            solve(ros,dictionary,list,ans+left+" ");

            //ans.delete(del,ans.length());

            }

        }

        return;

    }

}

Time complextiy : O(n + 2^n)  n→ for string length and 2^n for all possible partition 

space complexity : O(n*2^n) stack space and for extra ArrayList

public static ArrayList<String> wordBreak(String s, ArrayList<String> dictionary) {

        ArrayList<String> ans=new ArrayList<>();

        //if String s is already present in the list  dictionary just add it to ans list;

        if(dictionary.contains(s)) ans.add(s);

        for(int i=1;i<=s.length();i++){

            //takes left part as substring;

            String left=s.substring(0,i);

            //when the left part of a String is found in dicitionary just recursive call for the remaining part and add both to ans List;

            if(dictionary.contains(left)){

                List<String> temp=wordBreak(s.substring(i), dictionary);

                //after recurrsive call add all stored elementfrom temp to ans list;

                for(String sen: temp){

                    ans.add(left+" "+sen);

                }

            }

        }

        return ans;

    }

import java.util.* ;
import java.io.*; 
import java.util.ArrayList;

public class Solution {

	public static ArrayList<String> wordBreak(String s, ArrayList<String> dictionary) {
		ArrayList<String> list=new ArrayList();
		solve(s,dictionary,new StringBuilder(),list);
		return list;
	}
	public static void solve(String s, ArrayList<String> dictionary,StringBuilder str,ArrayList<String> list){
		if(s.length()==0){
			list.add(str.toString());
			return;
		}

		StringBuilder word=new StringBuilder();
		for(int i=0;i<s.length();i++){
			word.append(s.charAt(i));

			if(dictionary.contains(word.toString())){
				str.append(word+" ");
				solve(s.substring(i+1),dictionary,str,list);
				int del=str.lastIndexOf(word.toString());
				str.delete(del,str.length());
			}
		}
	}
}

#include <bits/stdc++.h> 
void wordBreak(string &s, vector<string> &dic, vector<string> &ans, string temp,int start){
    if(start == s.size()){
        temp.pop_back();
        ans.push_back(temp);
        return;
    }

    for(int i = start;i<s.size();i++){
        string word = s.substr(start,i-start+1);

        if(find(dic.begin(),dic.end(),word) != dic.end()){
            wordBreak(s,dic,ans,temp+word+" ",i+1);
        }
    }
}

vector<string> wordBreak(string &s, vector<string> &dictionary)
{
    vector<string> ans;
    
    wordBreak(s,dictionary,ans,"",0);

    return ans;

}

#include <bits/stdc++.h>

using namespace std;

void backtrack(string &s, unordered_set<string> &dictionary, vector<string> &result, string current, int start) {

    if (start == s.length()) {

        result.push_back(current);

        return;

    }

    for (int i = start; i < s.length(); i++) {

        string word = s.substr(start, i - start + 1);

        if (dictionary.find(word) != dictionary.end()) {

            string new_current = current.empty() ? word : current + " " + word;

            backtrack(s, dictionary, result, new_current, i + 1);

        }

    }

}

vector<string> wordBreak(string &s, vector<string> &dictionary) {

    unordered_set<string> dict(dictionary.begin(), dictionary.end());

    vector<string> result;

    backtrack(s, dict, result, "", 0);

    return result;

}

from os import *
from sys import *
from collections import *
from math import *

class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        curr = self.root

        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        
        curr.endOfWord = True
        

    def search(self, word: str) -> bool:
        curr = self.root

        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        
        return curr.endOfWord

def wordBreak(s, dictionary):
    trie = Trie()
    for word in dictionary:
        trie.insert(word)

    result = []
    n = len(s)
    def solve(i, curr):
        if i == n:
            result.append(curr.strip())
            return
        
        for j in range(i, n):
            word = s[i: j + 1]
            if trie.search(word):
                solve(j + 1, curr + word + " ")
    
    solve(0,  "")
    return result

def wordBreak(s, dictionary):
    def rec(i,w):
        if i==len(s):
            out.append(w)
            return
        for j in range(i,len(s)):
            if s[i:j+1] in dictionary:
                rec(j+1,w+s[i:j+1]+' ')

    out = []

    rec(0,'')
    return out

public class Solution {
	static ArrayList<String> ans = new ArrayList<>();
	private static void breakWord(String s, int ind, Set<String> set, StringBuilder sb){
		if(ind >= s.length()) {
			ans.add(sb.toString().trim());
			return;
		}

		String temp;
		int initialLength = sb.length();
		for(int i=ind+1;i<=s.length();i++){
			temp = s.substring(ind, i);
			if(set.contains(temp)){
				sb.append(temp).append(" ");
				breakWord(s, i, set, sb);
				sb.delete(initialLength, sb.length());
			}
		}
	}

	public static ArrayList<String> wordBreak(String s, ArrayList<String> dictionary) {
		// Write your code here.
		Set<String> set = new HashSet<>(dictionary);
		StringBuilder sb = new StringBuilder();
		breakWord(s, 0, set, sb);
		return ans;
	}
}