Word Break Problem in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Break Check for Simple Case

What is the output of this TypeScript code that checks if the string can be segmented into dictionary words?

DSA Typescript

function wordBreak(s: string, wordDict: string[]): boolean {
  const dp: boolean[] = Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordDict.includes(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

console.log(wordBreak("leetcode", ["leet", "code"]));

A false

B true

C SyntaxError

D TypeError

💡 Hint

Think about whether the string "leetcode" can be split into "leet" and "code" from the dictionary.

The string "leetcode" can be segmented as "leet" + "code", both are in the dictionary, so the function returns true.

❓ Predict Output

intermediate

Output for Word Break with No Possible Segmentation

What is the output of this TypeScript code when the string cannot be segmented into dictionary words?

DSA Typescript

function wordBreak(s: string, wordDict: string[]): boolean {
  const dp: boolean[] = Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordDict.includes(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

console.log(wordBreak("applepenapple", ["apple", "pen", "pine"]));

A true

B false

C ReferenceError

D RangeError

💡 Hint

Check if the string "applepenapple" can be segmented using the dictionary words.

The string "applepenapple" can be segmented as "apple" + "pen" + "apple", all in the dictionary, so the function returns true.

❓ Predict Output

advanced

Output of Word Break for Overlapping Dictionary Words

What is the output of this TypeScript code when the dictionary contains overlapping words?

DSA Typescript

function wordBreak(s: string, wordDict: string[]): boolean {
  const dp: boolean[] = Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordDict.includes(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

console.log(wordBreak("catsanddog", ["cat", "cats", "and", "sand", "dog"]));

A SyntaxError

B false

C TypeError

D true

💡 Hint

Try to segment "catsanddog" using the dictionary words, considering overlapping options.

The string "catsanddog" can be segmented as "cats" + "and" + "dog" or "cat" + "sand" + "dog", so the function returns true.

🔧 Debug

advanced

Identify the Error in Word Break Implementation

What error will this TypeScript code produce when run?

DSA Typescript

function wordBreak(s: string, wordDict: string[]): boolean {
  const dp: boolean[] = Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordDict.indexOf(s.substring(j, i)) !== -1) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

console.log(wordBreak(null as unknown as string, ["leet", "code"]));

A SyntaxError

B ReferenceError: wordBreak is not defined

C TypeError: Cannot read property 'length' of null

D No error, returns false

💡 Hint

Check what happens if the input string is null instead of a string.

Passing null as the string causes accessing s.length to throw a TypeError because null has no length property.

🚀 Application

expert

Number of Ways to Segment String Using Word Break Logic

Given the following TypeScript code that counts how many ways the string can be segmented into dictionary words, what is the output?

DSA Typescript

function wordBreakCount(s: string, wordDict: string[]): number {
  const dp: number[] = Array(s.length + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (wordDict.includes(s.substring(j, i))) {
        dp[i] += dp[j];
      }
    }
  }
  return dp[s.length];
}

console.log(wordBreakCount("catsanddog", ["cat", "cats", "and", "sand", "dog"]));

A 2

B 1

C 3

D 0

💡 Hint

Count all possible segmentations of "catsanddog" using the dictionary words.

There are two ways: "cats" + "and" + "dog" and "cat" + "sand" + "dog". So the count is 2.