Salesforce OA 2023 - Kitty in horror house

Problem Description:

Kitty is locked inside a horror house where there are distinct random words written on the wall. Inside the house, Kitty encounters a ghost who offers to help on one condition. The ghost will give Kitty a word, and Kitty must determine whether she can create this word using the words written on the walls of the horror house. If she can, the ghost will take her out of the house, otherwise, she will be stuck forever.

You need to write an algorithm to help Kitty escape. Your task is to determine if the given word can be segmented into a sequence of one or more dictionary words from the wall.

Return true if Kitty can create the word, otherwise return false.

Note: Words in the dictionary can be reused multiple times when forming the word.

Input Format:

• A string s representing the word given by the ghost.
• A list wordDict[] consisting of words written on the wall.

Output Format:

• Return true if the word s can be formed using words from the dictionary, otherwise return false.

Constraints:

• 1 <=s.length<=300
• 1<=wordDict.length<=1000
• 1<=wordDict[i].length<=20
• The string s and all words in wordDict[] consist of lowercase English letters.

Sample Testcase:

Example 1:

Input:

s = "hackerrank"
wordDict = ["hacker", "rank"]

Output:

true

Explanation:
Kitty can create the word "hackerrank" using "hacker" and "rank" from the word dictionary.

Example 2:

Input:

s = "penappleapple"
wordDict = ["apple", "pen"]

Output:

true

Example 3:

Input:

s = "catsanddogs"
wordDict = ["cats", "dogs", "pineapple"]

Output:

false