Word Break Problem (Using HashMap and DP)

Posted by N.K. Chauhan on Nov 24, 2022

Given a string "s" and an array of words "words," find out if "s" can be segmented into a space-separated sequence of words contained in the array.

Note: From the array "words []," each word can be taken any number of times and in any order.

Example
Input: s="busylivingdying", words[] = {"Get", "busy", "living", "or", "get", "dying"}, Output: true

Example
Input: s="liveagainonce", words[] = {"you", "only", "live", "once"}, Output: false


Solutions

Method 1: In O(n^2) time and O(n) space

This method includes using an extra "set" to store words so that we can check their existence in O(1) time.

The idea is to keep appending the current character to the "tmp" string and check if "tmp" is present in the array.

If any instance of the "tmp" string is present in the array, check the remaining sub-string recursively.

If "tmp" and the remaining sub-string are both recursively present in the array, than return "true"; otherwise, return "false".

Complexity

The time complexity of this solution is O(n^2) and space complexity is O(n).

Related


Print all Subsets (Power Set) of a given array

Longest substring without repeating characters

Find a triplet in an array that sums to a given number

Merge two sorted arrays in O(1) space

Count the number of inversions in an array - in O(n log n) time

Program to print Intersection of two sorted arrays

Program to print Union of two sorted arrays

Rain water trapping problem - O(n) time & O(n) space

Two Sum - return index of a pair of array elements with a given sum

Print all possible permutations of an Array in O(1) space