Word Formation From a Dictionary Using a Trie

Given a dictionary stored in a trie and a target word, return true if the target can be formed by joining exactly two dictionary words.

Example

Text

dictionary: ["the", "hello", "there", "answer", "any", "by", "world", "their", "abc"]

"helloworld"   true    hello + world
"thereby"      true    there + by   ("the" + "reby" fails, so keep looking)
"thebye"       false

Brute force: search both halves at every split

For each split position i, search the trie for word.substring(0, i) and for word.substring(i). A trie node is an object with an array of 26 child references, where null means "no such child".

Java

public class Main {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    static void insert(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) node.children[idx] = new TrieNode();
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    static boolean search(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            node = node.children[word.charAt(i) - 'a'];
            if (node == null) return false;
        }
        return node.isEnd;
    }

    static boolean canForm(TrieNode root, String word) {
        for (int i = 1; i < word.length(); i++) {
            if (search(root, word.substring(0, i)) && search(root, word.substring(i))) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        TrieNode root = new TrieNode();
        for (String w : new String[] {"the", "hello", "there", "answer", "any", "by", "world", "their", "abc"}) {
            insert(root, w);
        }
        System.out.println(canForm(root, "helloworld") + " " + canForm(root, "thereby") + " " + canForm(root, "thebye"));
    }
}

Output

true true false

Time: O(L²): L - 1 split positions, and each one searches up to L characters (and substring copies up to L characters). Space: O(L) for the copied substrings.

This repeats work: searching word.substring(0, 3), then word.substring(0, 4), then word.substring(0, 5) walks the same first characters again each time.

Optimal: walk the prefix once

Walk the target down the trie one character at a time, from the root. After each step, the current node represents the prefix word.substring(0, i + 1):

If the path breaks (no child for the next character), no longer prefix can be a dictionary word, so stop and return false.
If the current node has isEnd set, the prefix is a dictionary word. Check whether the rest, word.substring(i + 1), is a word too.

The walk visits each character of the target once, and only tries the second-half search at positions where the first half really is a word.

Walkthrough with "thereby":

position	prefix	node exists?	is a word?	check the rest
0	t	yes	no
1	th	yes	no
2	the	yes	yes	"reby" → not a word, continue
3	ther	yes	no
4	there	yes	yes	"by" → word → return true

Java

public class Main {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    static void insert(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) node.children[idx] = new TrieNode();
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    static boolean search(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            node = node.children[word.charAt(i) - 'a'];
            if (node == null) return false;
        }
        return node.isEnd;
    }

    static boolean canForm(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            node = node.children[word.charAt(i) - 'a'];
            if (node == null) return false; // no dictionary word starts with word[0..i]
            int split = i + 1;
            if (node.isEnd && split < word.length() && search(root, word.substring(split))) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        TrieNode root = new TrieNode();
        for (String w : new String[] {"the", "hello", "there", "answer", "any", "by", "world", "their", "abc"}) {
            insert(root, w);
        }
        System.out.println(canForm(root, "helloworld") + " " + canForm(root, "thereby") + " " + canForm(root, "thebye"));
        System.out.println(canForm(root, "byby")); // the same word twice
    }
}

Output

true true false
true

Time: O(L + p · L), where p is the number of dictionary words that are prefixes of the target. In the worst case that's still O(L²), but usually p is small, and the walk stops early when no dictionary word matches the start. Space: O(L) for the substring copy made at each split attempt.

split < word.length() makes sure the second word isn't empty. Without it, a target that is itself a single dictionary word would count as "word + nothing".

Word Break (LeetCode 139) allows splitting into any number of dictionary words. The same trie walk becomes a dynamic program: can[i] means word.substring(0, i) can be built. From each i with can[i] true, walk the trie from position i and set can[j] for every j where the walk passes an end node.

Java

public class Main {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    static void insert(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) node.children[idx] = new TrieNode();
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    static boolean wordBreak(TrieNode root, String word) {
        int n = word.length();
        boolean[] can = new boolean[n + 1];
        can[0] = true;
        for (int start = 0; start < n; start++) {
            if (!can[start]) continue;
            TrieNode node = root;
            for (int j = start; j < n; j++) {
                node = node.children[word.charAt(j) - 'a'];
                if (node == null) break;
                if (node.isEnd) can[j + 1] = true;
            }
        }
        return can[n];
    }

    public static void main(String[] args) {
        TrieNode root = new TrieNode();
        for (String w : new String[] {"apple", "pen", "applepen", "pine", "pineapple", "cats", "dog", "sand", "and", "cat"}) {
            insert(root, w);
        }
        System.out.println(wordBreak(root, "pineapplepenapple") + " " + wordBreak(root, "catsandog"));
    }
}

Output

true false

Time: O(L²) in the worst case. Space: O(L).

Word Break covers this problem in full, with a HashSet instead of a trie.

Brute force: search both halves at every split

Optimal: walk the prefix once

Related: any number of words