One Sentence (string) is given. find out the words, that has length even and greater than equal to 4 (e.g. 4,6,8.. etc.) and separate them with space.
e.g. Given String : “abcd abc abcde abcdef”
Output...read more

In this solution, we will try to generate all prefixes and If we want a prefix present in the string then we will recur for the remaining string.

Steps:

1. Store all strings of A on the hash ma...read more

In this solution, we will use the Overlapping Subproblems property. We will store the already calculated result in a dp array.

Here we will store the result of our recursion in a dp array. 

    We can implement the above approach by – 

1. Store all strings of A on the hash map.
2. Declare a function wordBreakHelper which will take three arguments: string, start, and dp array.
3. If start equals the length of the string then return true.
4. Run a loop from i = 1 to the length of the string.
5. If dp[start] is already calculated then return it.
6. If substring from 0 to i exists in the map and recursion of the remaining string gives true then return true.
7. After running the loop, return false.

O(N),  where N is the length of the string target.

We are storing all strings in a hashmap which will take O(N) space.

Hence the space complexity will be O(N).

O(N^2), where N is the length of the string target.

In this case, we are generating and checking all subarrays of the target string which will take O(N) time.

Hence the overall complexity will be O(N^2). 

'''

    Time Complexity: O(N ^ 2)

    Space Compelxity: O(N)

    

    Where N is the length of the target string.

'''



hashMap = dict()



def wordBreakHelper(s, start, dp):

    

    # Base case.

    if start == len(s):

        dp[start] = 1

        return dp[start]

    

    # If the result is already calculated, then return it.

    if dp[start] != -1:

        return dp[start]

    

    # Run a loop from 1 to length of the target string.

    for i in range(start + 1, len(s) + 1, 1):

        '''

        If substring from 0 to i exist in hash map

        and remaining string recurs true

        '''

        if s[start:i] in hashMap:

            if wordBreakHelper(s, i, dp):

                dp[start] = 1

                return dp[start]

        

    dp[start] = 0

    return dp[start]





def wordBreak(arr, n, target):

    

    # Clear hash map for current test case.

    hashMap.clear()

    

    # Insert all strings into hashmap.

    for s in arr:

        hashMap[s] = 1

    

    # Declare dp array ans initialise all values with -1.

    dp = [-1 for i in range(len(target) + 2)]

    

    # Call wordBreakHelper to return answer.

    return wordBreakHelper(target, 0, dp)

/*

    Time Complexity  : O(N ^ 2)

    Space Complexity : O(N)



    Where N is the length of target string.

*/



#include 



// Declare a hash map.

unordered_set < string > hashMap;



bool wordBreakHelper(string & s, int start, vector < int > & dp) {

    // Base case

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

        return dp[start] = 1;

    }



    // If result is already calculated then return it.

    if (dp[start] != -1) {

        return dp[start];

    }



    // Run a loop from 1 to length of target string.

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

        /*

            If substring from 0 to i exist in hash map

            And remaining string recurs true.

        */

        if (hashMap.find(s.substr(start, i - start)) != hashMap.end()) {

            if (wordBreakHelper(s, i, dp)) {

                return dp[start] = 1;

            }

        }

    }



    // If no solution exist then return false.

    return dp[start] = 0;

}



bool wordBreak(vector < string > & arr, int n, string & target) {

    // Clear hash map for current test case.

    hashMap.clear();



    // Insert all strings of a into hashmap.

    for (string s: arr) {

        hashMap.insert(s);

    }



    // Declare dp array and initialize all values with -1.

    vector < int > dp(target.size() + 1, -1);



    // Call wordBreakHelper to return answer.

    return wordBreakHelper(target, 0, dp);

}

/*

    Time Complexity  : O(N ^ 2)

    Space Complexity : O(N)



    Where N is the length of target string.

*/



import java.util.HashSet;



public class Solution {



    // Declare a hash map.

    static HashSet < String > hashMap = new HashSet < > ();



    public static boolean wordBreakHelper(String s, int start, int[] dp) {

        // Base case.

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

            dp[start] = 1;

            return true;

        }



        // If result is already calculated then return it.

        if (dp[start] != -1) {



            return dp[start] != 0;

        }



        // Run a loop from 1 to length of target string.

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

            /*

              If substring from 0 to i exist in hash 

              map And remaining string recurs true.

            */

            if (hashMap.contains(s.substring(start, i))) {

                if (wordBreakHelper(s, i, dp)) {

                    dp[start] = 1;

                    return true;

                }

            }

        }



        // If no solution exist then return false.

        dp[start] = 0;

        return false;

    }



    public static boolean wordBreak(String[] arr, int n, String target) {

        // Clear hash map for current test case.

        hashMap.clear();



        // Insert all strings of a into hashmap.

        for (String s: arr) {

            hashMap.add(s);

        }



        // Declare dp array and initialize all values with -1.

        int[] dp = new int[target.length() + 1];

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

            dp[i] = -1;



        // Call wordBreakHelper to return answer.

        return wordBreakHelper(target, 0, dp);

    }

}

In this solution, we will Bottom Up dp.

Here first we will store all strings of A in a hashmap. Then we will declare a dp array and run two loops and mark dp[i] true if and only if there ex...read more

In this solution, we will use a graph to represent all possible solutions. The vertices are the position of first character of a word and edges will represent the whole word.

We will use a ...read more