DEV Community

Cover image for 140. Word Break II
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

140. Word Break II

140. Word Break II

Hard

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

  • Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
  • Output: ["cats and dog","cat sand dog"]

Example 2:

  • Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
  • Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
  • Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

  • Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
  • Output: []

Constraints:

  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.
  • Input is generated in a way that the length of the answer doesn't exceed 105.

Solution:

class Solution {

    private $map = array();

    /**
     * @param String $s
     * @param String[] $wordDict
     * @return String[]
     */
    function wordBreak($s, $wordDict) {
        if(array_key_exists($s, $this->map)) {
            return $this->map[$s];
        }

        $result = array();

        if(strlen($s) == 0){
            $result[] = "";
            $this->map[""] = $result;
            return $result;
        }

        foreach($wordDict as $word) {
            if(strpos($s, $word) === 0){
                $subWords = $this->wordBreak(substr($s, strlen($word)), $wordDict);
                foreach($subWords as $subWord) {
                    $result[] = $word . (strlen($subWord) > 0 ? " " : "") . $subWord;
                }
            }
        }

        $this->map[$s] = $result;
        return $result;
    }
}
Enter fullscreen mode Exit fullscreen mode

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Billboard image

Synthetic monitoring. Built for developers.

Join Vercel, Render, and thousands of other teams that trust Checkly to streamline monitor creation and configuration with Monitoring as Code.

Start Monitoring

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay