Katkat
Back

Check if all substrings are dictionary words

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates string-processing skills such as substring enumeration and membership testing against a dictionary, along with algorithmic reasoning about correctness and complexity.

You are given a string s (letters only) and access to an English dictionary dict (a set of valid words).

Return true if every contiguous substring of s with length >= 3 is a valid dictionary word (i.e., for all i, j with 0 <= i <= j < n and j - i + 1 >= 3, s[i..j] ∈ dict). Otherwise return false.

Clarifications:

  • Substring means contiguous.
  • You may assume dictionary lookups are available (e.g., dict.contains(word)), or you can preprocess the dictionary.

Example:

  • If s = "cats", you must check "cat", "ats", and "cats" (and any other substrings of length >= 3).