Word Formation Using a Hash Table

Given a dictionary of words and a target word, return true if the target can be formed by joining exactly two words from the dictionary. The same dictionary word may be used twice.

Example

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

"helloworld"   true    hello + world
"theanswer"    true    the + answer
"thebye"       false   "the" + "bye": "bye" isn't in the dictionary

Brute force: try every pair of dictionary words

For every pair (first, second), check whether the target equals first + second. Instead of building the concatenation, check that the lengths add up, that the target starts with first, and that it ends with second.

public class Main {
    static boolean canForm(String[] dict, String word) {
        for (String first : dict) {
            for (String second : dict) {
                if (first.length() + second.length() == word.length()
                        && word.startsWith(first) && word.endsWith(second)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        String[] dict = {"the", "hello", "there", "answer", "any", "by", "world", "their", "abc"};
        System.out.println(canForm(dict, "helloworld") + " " + canForm(dict, "theanswer") + " " + canForm(dict, "thebye"));
    }
}

true true false

Time: O(d² · L) for d dictionary words and a target of length L. Space: O(1).

This gets slow for a large dictionary: 100,000 words means 10¹⁰ pairs.

Optimal: try every split point

The target has only L - 1 ways to split into two non-empty parts. For each split position i, the target is valid if both word.substring(0, i) and word.substring(i) are dictionary words. Put the dictionary in a HashSet so each check is O(1) (plus hashing the substring).

Walkthrough with "theanswer":

import java.util.HashSet;
import java.util.Set;

public class Main {
    static boolean canForm(Set<String> dict, String word) {
        for (int i = 1; i < word.length(); i++) {
            if (dict.contains(word.substring(0, i)) && dict.contains(word.substring(i))) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Set<String> dict = new HashSet<>(java.util.List.of("the", "hello", "there", "answer", "any", "by", "world", "their", "abc"));
        System.out.println(canForm(dict, "helloworld") + " " + canForm(dict, "theanswer") + " " + canForm(dict, "thebye"));
        System.out.println(canForm(dict, "byby")); // the same word twice
        System.out.println(canForm(dict, "a") + " " + canForm(dict, ""));
    }
}

true true false
true
false false

Time: O(L²): L - 1 splits, and substring plus hashing each part costs up to O(L). That doesn't depend on the dictionary size. Space: O(d) for the set.

substring copies the characters it returns, so each split allocates two short strings. Splitting at an index inside a surrogate pair (a character outside the Basic Multilingual Plane) would cut it in half. For plain ASCII input, every index is a safe split point.

Related problems

• The trie version of this problem walks the target through a trie, which checks all prefixes in a single pass.
• Word Break (LeetCode 139) allows any number of words. It uses dynamic programming: can[i] is true if the first i characters can be built, and can[i] = any can[j] && dict contains word.substring(j, i).

Edge cases

• Target shorter than 2 characters: it can't be split into two non-empty words, so the answer is false.
• Empty dictionary: false.