Introduction

Finding all English-word substrings means scanning a string for every contiguous slice that is also present in a dictionary. The hard part is not the substring generation itself; it is doing the lookup efficiently enough that longer inputs do not explode into unnecessary work.

Start With a Dictionary-Based Scan

If the problem is "find all valid dictionary words that appear as substrings," a dictionary set is the right baseline. A hash set gives constant-time membership checks, which keeps the implementation simple and fast enough for many workloads.

The naive algorithm considers every start index and every end index after it. That produces O(n^2) substrings, and each substring creation can cost additional time. Still, it is a good place to start because it is easy to verify.

1def find_word_substrings(text, dictionary):
2    found = []
3
4    for start in range(len(text)):
5        for end in range(start + 1, len(text) + 1):
6            candidate = text[start:end].lower()
7            if candidate in dictionary:
8                found.append((candidate, start, end))
9
10    return found
11
12dictionary = {"cat", "cats", "sand", "and", "dog"}
13print(find_word_substrings("catsanddog", dictionary))

The result includes the word plus its position. That matters in practice because repeated words can occur at different offsets, and many downstream tasks need those locations.

Reduce Work With Maximum Word Length

Real dictionaries have a longest word. Once you know that bound, there is no reason to keep extending substrings past it.

1def find_word_substrings_bounded(text, dictionary):
2    max_len = max(len(word) for word in dictionary)
3    found = []
4
5    for start in range(len(text)):
6        stop = min(len(text), start + max_len)
7        for end in range(start + 1, stop + 1):
8            candidate = text[start:end].lower()
9            if candidate in dictionary:
10                found.append((candidate, start, end))
11
12    return found
13
14dictionary = {"a", "an", "and", "cat", "cats", "dog", "sand"}
15print(find_word_substrings_bounded("catsanddog", dictionary))

This does not change the worst-case shape completely, but it makes the scan much cheaper when the input is long and the word list contains reasonably short entries.

Use a Trie When the Dictionary Is Large

A trie helps when you have a large word list and you want to stop early as soon as a prefix is impossible. Instead of slicing every possible substring and asking "is this a word," you walk forward character by character and abandon the search the moment a prefix no longer exists.

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_word = False
5
6
7def build_trie(words):
8    root = TrieNode()
9    for word in words:
10        node = root
11        for ch in word.lower():
12            node = node.children.setdefault(ch, TrieNode())
13        node.is_word = True
14    return root
15
16
17def find_with_trie(text, words):
18    root = build_trie(words)
19    found = []
20    lowered = text.lower()
21
22    for start in range(len(lowered)):
23        node = root
24        for end in range(start, len(lowered)):
25            ch = lowered[end]
26            if ch not in node.children:
27                break
28            node = node.children[ch]
29            if node.is_word:
30                found.append((lowered[start:end + 1], start, end + 1))
31
32    return found
33
34
35print(find_with_trie("catsanddog", {"cat", "cats", "and", "sand", "dog"}))

The trie version pays an upfront build cost, but it avoids a large number of hopeless substring checks.

Decide Whether You Need Substrings or Segmentation

This question is often confused with word breaking. Substring search asks for any contiguous English word anywhere inside the string. Word segmentation asks whether the whole string can be split into valid words, often with no unused characters.

For example, in "catsanddog", the substrings "cat", "cats", "sand", "and", and "dog" are all valid findings. A segmenter would go further and try to assemble a complete parse such as "cats" + "and" + "dog".

If your real goal is segmentation, dynamic programming is usually a better fit than raw substring enumeration.

Handling Normalization

Dictionary lookups are only as good as your normalization rules. English text may contain uppercase letters, apostrophes, hyphens, and punctuation. You should define whether "don't", "co-op", or "e-mail" count as words, then normalize both the dictionary and the input the same way.

If you skip that step, the algorithm can look correct while silently missing valid matches.

1import re
2
3def normalize(text):
4    return re.sub(r"[^a-z']", "", text.lower())
5
6print(normalize("Don't!"))

Common Pitfalls

The most common pitfall is using a list for the dictionary instead of a set or trie. That turns each lookup into a linear scan and makes the whole algorithm much slower.

Another issue is creating substrings repeatedly in languages where slicing copies data. In performance-sensitive code, consider walking indices or prefixes rather than allocating new strings for every candidate.

Case handling is also easy to get wrong. If the input is lowercased but the dictionary is not, some matches disappear for no obvious reason.

Finally, make sure the requirement really is "all substrings." If the caller wants only the longest matches, only distinct words, or only segmentations that cover the full string, the implementation should change accordingly.

Summary

• A hash-set dictionary is the simplest correct solution for substring lookup.
• Bounding the search by maximum dictionary word length avoids pointless checks.
• A trie is useful when the dictionary is large and prefix pruning matters.
• Substring search and full-word segmentation are different problems.
• Normalize input and dictionary consistently or valid words will be missed.