Problem 1408

Abstract / Summary

Find if any string in a list is a substring of another string in the same list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1408.py

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        for v in words:
            for w in words:
                if w != v and w.find(v) != -1:
                    yield v
                    break # one match is enough
7 lines | 259 bytes | submitted November 10, 2023 | GitHub   14% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 70% (300k+ submissions).

Typical patterns to solve this problem:
  • Array
  • String
  • String Matching
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a Solution class with a single method stringMatching. The method receives a list of strings and produces those strings that appear as substrings of at least one other string in the same list. It does so by iterating over every possible ordered pair of words, testing for the substring relationship, and yielding a word as soon as a match is found. The use of a generator (yield) means that results are produced lazily, which can be advantageous when the caller does not need the entire collection at once.

Core Logic

The algorithm consists of three distinct stages: the outer iteration over candidate substrings, the inner iteration over potential host strings, and the substring detection followed by early termination of the inner loop.

Outer Iteration

for v in words:

In this step each element v from the input list words is considered as a possible substring. The variable name v is used throughout the method to denote the candidate word.

Inner Iteration and Self-Exclusion

for w in words:
    if w != v and w.find(v) != -1:

For each candidate v, the method scans the entire list again, assigning each element to w. The condition w != v guarantees that a word is not compared with itself, preventing a trivial match. The call w.find(v) searches for the occurrence of v inside w. A return value other than -1 indicates that v is indeed a substring of w.

Yielding and Early Exit

        yield v
        break  # one match is enough

When a matching host string w is discovered, the candidate v is emitted via yield. The subsequent break exits the inner loop immediately, ensuring that each qualifying word is produced only once, regardless of how many host strings contain it. This early exit reduces unnecessary comparisons after the first successful match.

Edge Cases Handled

The implementation naturally accommodates several boundary conditions without additional code.

When the input list is empty, the outer loop has no elements to iterate over, so the generator produces no output. A single-element list also results in no output because the inner loop will only encounter the same word, and the w != v guard prevents a self-match.

If the list contains duplicate strings, each occurrence is treated independently in the outer loop. However, because the inner loop excludes the current instance (w != v), a duplicate can still be identified as a substring of another duplicate, leading to the duplicate being yielded.

An empty string ("") is a valid substring of any other string, including another empty string. The condition w != v prevents an empty string from matching itself, but an empty string will be yielded if there exists any other string in the list, because w.find("") returns 0 for any non-empty w.

Words that are substrings of multiple other words are still yielded only once, thanks to the break that stops further scanning after the first match.

Performance Characteristics

The algorithm avoids constructing intermediate collections by using a generator. This lazy evaluation means that memory consumption is limited to the current iteration state rather than the full result set.

The inner loop includes an early termination (break) as soon as a match is found. This prevents the method from continuing to compare the same candidate v against the remaining words once a qualifying host has been identified, reducing the total number of substring checks.

The use of the built-in str.find method leverages the highly optimized C implementation of substring search provided by the Python runtime. This choice is typically faster than manual character-by-character scanning.

Overall, the design balances simplicity with practical efficiency by combining early exit, built-in string search, and lazy result generation.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a big treasure box full of name tags. Some tags spell out a whole name like apple, while other tags spell out a smaller piece of a name like app. This code is like a little helper that looks through every name tag in the box and compares it to all the others. It asks if one name tag is hidden inside another one. If the helper finds that a smaller name tag is hiding inside a bigger one, it puts that smaller tag into a special pile to keep. The helper checks every single tag one by one, and if it sees a match, it remembers it and then moves on to look at the next tag until it is all finished.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 7 | μ = 5.96 | σ = 1.83

Complexity Analysis

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Python Go Rust TS
Progiez C++ Java Python
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fsq C++
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
Shamik07 Dart
varunu28 Java
withaarzoo C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, Rust, TypeScript
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fsq C++
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
Shamik07 Dart
varunu28 Java
withaarzoo C++
30 links | 18 authors | 11 languages

Videos

7 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

5 solutions   November 10, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality