CodingGyan

Word Break

hard Strings

Problem

The first line is a word s. The second line holds a dictionary of words separated by spaces. Print true if s can be cut into pieces so that every piece is a word of the dictionary (a dictionary word can be used many times), else false. Use dynamic programming: reachable[i] tells if the first i letters can be built.

Constraints

  • 1 <= word length <= 1000
  • 1 <= dictionary words <= 1000

Examples

Input

applepenapple
apple pen

Output

true

Solutions

Best approachTime O(n^2)Space O(n)

Greedy cutting fails (for leetcode the first piece could be a wrong one in other examples), and trying every way of cutting is exponential. The table reachable[] remembers for each prefix if it can be built, so each position is solved once: O(n^2) set lookups.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Can it be cut?
 * Input   : A word, then a dictionary line.
 * Output  : true or false.
 * Approach: DP over the cut points.
 * Time    : O(n^2)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static boolean solve(String[] lines) {
        // Step 1: Read the word and put the dictionary words in a set for fast lookup.
        String word = lines[0];
        java.util.Set<String> dictionary = new java.util.HashSet<>(java.util.Arrays.asList(lines[1].split(" ")));
        // Step 2: reachable[i] is true when the first i letters can be cut into dictionary words. The empty start is reachable.
        boolean[] reachable = new boolean[word.length() + 1];
        reachable[0] = true;
        for (int end = 1; end <= word.length(); end++) {
            // Step 3: Try every cut point. The first part must be reachable and the rest must be a word.
            for (int cut = 0; cut < end && !reachable[end]; cut++) {
                if (reachable[cut] && dictionary.contains(word.substring(cut, end))) {
                    reachable[end] = true;
                }
            }
        }
        return reachable[word.length()];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(solve(lines));
    }
}
Hints (1)
  1. Why does a greedy longest-word-first cut fail?

Try these next