Trie contains "cat", "bat", "rat". Process "cattle".
Walk through trie with "cattle":
- 'c' → exists, not a root end
- 'a' → exists, not a root end
- 't' → exists, IS a root end
Found root "cat" at length 3. Replace "cattle" with "cat".
Process "battery": 'b' → 'a' → 't' → root end. Replace with "bat".
Process "the": 't' exists but 'h' doesn't follow. No root found. Keep "the".
Build trie: . Process each word: . Total: where is total root characters and is sentence length.