Word Break

[jsartisan]

Info

difficulty: medium
title: Word Break
type: question
template: typescript
tags: javascript, blind75, dynamic-programming, string

Question

Given a string s and a dictionary of strings wordDict, determine if s can be segmented into a space-separated sequence of dictionary words.

Rules:

• Dictionary words can be reused unlimited times
• All dictionary words are unique
• Not all dictionary words must be used

Constraints:

• 1 ≤ s.length ≤ 200
• 1 ≤ wordDict.length ≤ 100
• 1 ≤ wordDict[i].length ≤ 20
• All strings contain only lowercase English letters

Examples:

// Example 1:
console.log(wordBreak("neetcode", ["neet","code"]));
// Output: true
// Explanation: "neetcode" = "neet" + "code"

// Example 2:
console.log(wordBreak("applepenapple", ["apple","pen"]));
// Output: true
// Explanation: "applepenapple" = "apple" + "pen" + "apple"

// Example 3:
console.log(wordBreak("catsincars", ["cats","cat","sin","in","car"]));
// Output: false
// Explanation: Cannot be segmented with given words

Template

index.ts

export function wordBreak(s: string, wordDict: string[]): boolean {

}

index.test.ts

import { wordBreak } from './index';

describe('wordBreak', () => {
  test('Example 1: Simple split', () => {
    expect(wordBreak("neetcode", ["neet","code"])).toBe(true);
  });

  test('Example 2: Reuse words', () => {
    expect(wordBreak("applepenapple", ["apple","pen"])).toBe(true);
  });

  test('Example 3: Cannot segment', () => {
    expect(wordBreak("catsincars", ["cats","cat","sin","in","car"])).toBe(false);
  });

  test('Single word match', () => {
    expect(wordBreak("hello", ["hello"])).toBe(true);
  });

  test('Empty string', () => {
    expect(wordBreak("", ["test"])).toBe(true);
  });

  test('No possible combination', () => {
    expect(wordBreak("cars", ["car","ca","rs"])).toBe(false);
  });

  test('Multiple valid splits', () => {
    expect(wordBreak("pineapplepen", ["pine","pineapple","apple","pen"])).toBe(true);
  });

  test('Overlapping words', () => {
    expect(wordBreak("foofoo", ["foo"])).toBe(true);
  });

  test('Single character words', () => {
    expect(wordBreak("abcde", ["a","b","c","d","e"])).toBe(true);
  });

  test('Long string with short words', () => {
    expect(wordBreak("aaaaaaa", ["aaa","aaaa"])).toBe(true);
  });
});

[github-actions[bot]]

300 - Pull Request updated.