Abstract / Summary

Given two sentences, determine if they are similar by checking if each word in one appears in the other with the same frequency.

Note

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

This problem is ranked as

and has an acceptance rate of about 48% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• String
• Two Pointers

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.

Overview

The provided implementation determines whether two sentences can be considered similar under the rule that one sentence can become the other by inserting an arbitrary (possibly empty) substring into the shorter sentence. The algorithm works by breaking each sentence into word tokens, aligning the shorter sentence against the longer one, and then stripping matching words from both the beginning and the end. If, after these removals, the shorter sentence is empty, the two original sentences satisfy the similarity condition.

Key Steps

Splitting Input

The first operation tokenizes each input string on spaces, producing two lists of words.

s1 = sentence1.split(" ")
s2 = sentence2.split(" ")

These lists, s1 and s2, serve as the mutable structures that the rest of the algorithm manipulates.

Normalizing Length

To simplify subsequent logic, the code ensures that s1 always refers to the list with fewer or equal words. If the original sentence1 contains more words, the two lists are swapped.

if len(s1) > len(s2):
    s1, s2 = s2, s1

By guaranteeing that s1 is the shorter list, the algorithm can focus on eliminating all of its elements while comparing against the longer list.

Trimming Common Prefix

The algorithm removes matching words from the start of both lists. It repeatedly checks whether the first elements are equal and, if so, discards them from both s1 and s2.

while s1 and s1[0] == s2[0]:
    s1.pop(0)
    s2.pop(0)

This loop stops when either list becomes empty or the leading words differ, effectively aligning the remaining portions of the sentences after any shared beginning.

Trimming Common Suffix

After the prefix removal, the code performs a similar operation on the ends of the lists. It removes matching trailing words until a mismatch is encountered or one list is exhausted.

while s1 and s1[-1] == s2[-1]:
    s1.pop()
    s2.pop()

By handling the suffix after the prefix, the algorithm isolates the segment of the longer sentence that could correspond to the inserted substring.

Final Decision

The similarity condition is satisfied when all words of the shorter sentence have been eliminated by the prefix and suffix trimming. The final return statement reflects this check.

return not s1

If s1 is empty, the function returns True; otherwise, it returns False.

Edge Cases Handled

The implementation gracefully manages several boundary situations without additional conditional logic. When both input sentences are identical, the prefix loop consumes all words, leaving both lists empty, and the function correctly returns True. If one sentence is a single word and the other contains that word plus additional content, the prefix or suffix removal will eliminate the shared word, and the remaining shorter list will be empty, yielding a True result. When one sentence is empty (i.e., an empty string), the split operation produces a list containing a single empty string element; however, because the algorithm treats empty strings as tokens, the subsequent loops will not remove any elements, and the final check will correctly evaluate the similarity based on the presence or absence of words. Cases where there is no common prefix or suffix are also covered: the loops simply do not execute, and the final decision depends on whether the shorter list was already empty.

Performance Optimizations

The code leverages in-place list modifications (pop(0) and pop()) to avoid creating additional data structures during the trimming phases. By operating directly on the original token lists, it reduces memory overhead. The early length normalization ensures that the number of iterations in both while loops is bounded by the size of the shorter sentence, preventing unnecessary comparisons against the longer list. Additionally, the use of short-circuit logical checks (while s1 and ...) prevents out-of-range accesses, allowing the loops to terminate as soon as the shorter list is exhausted. This approach yields a concise execution path that scales linearly with the number of words in the shorter sentence.

Imagine two long paper trains made of word blocks. The goal is to see if these trains are built from the same pieces, even if one has a big extra section stuck right in the middle of it.

First, the code takes the two sentences and breaks them into a line of individual words. It looks at the two lines and makes sure the shorter train is always being compared against the longer one so the math stays neat.

Next, the computer looks at both trains starting from the front. If the very first words match, it pulls those words off and sets them aside. It keeps doing this until it finds a word that does not match or until one train runs out of pieces.

After that, the computer goes to the back ends of the trains. It checks the very last words and pulls them off if they are the same. It keeps peeling these off like stickers until it hits a pair that is different or until the train runs out of words.

If the smaller train has no pieces left after those two steps, it means all its words were found at the start or the end of the longer train in the right order. This proves that the sentences are essentially the same.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

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	JS		Go	TS
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	fsq	C++
	JoshCrozier				JS
	lkwq007			Python
	suxrobGM					C#
	varunu28		Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
withaarzoo	C++

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