Abstract / Summary

Check if a given string can be formed by concatenating the start of each string in an array in order.

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 53% (100k+ 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 Solution.isPrefixString method determines whether a target string s can be formed by concatenating a prefix of the given list words. It walks through the list sequentially, building a cumulative string and checks for an exact match once the length of the built string equals the length of s. If the cumulative length exceeds that of s, the search stops early and the method returns False.

Key Steps

The method begins by initializing an empty accumulator:

have = ""

It then iterates over each word in the input list:

for w in words:

During each iteration the current word is appended to the accumulator:

have += w

After the concatenation, the length of the accumulator is compared with the length of the target string. When the lengths match, a direct equality test decides the result:

if len(have) == len(s):
    return have == s

If the accumulator becomes longer than the target, the loop terminates immediately because any further concatenation would only increase the mismatch:

if len(have) > len(s):
    break

If the loop finishes without returning, the method concludes that no prefix forms s and returns False:

return False

Edge Cases Handled

When words is empty, the loop body never executes, and the method returns False because the accumulator never reaches the length of s.

If s itself is an empty string, the accumulator starts as empty, but the method only checks for equality after at least one word has been added. Consequently, the method returns False for an empty target unless the first word is also empty, in which case the length comparison triggers the equality check and returns True.

When a word in words is longer than the remaining portion of s, the length-exceeding condition triggers the early break, preventing unnecessary processing of subsequent words.

If the concatenated prefix exactly matches s before consuming all words, the method returns True immediately, avoiding further iteration.

Performance Optimizations

The implementation avoids building the full concatenation of all words when it is unnecessary. By checking the length after each addition, it can stop as soon as the accumulator exceeds the target length, which prevents wasteful string operations for long lists.

The early return on exact length match eliminates the need to continue scanning the remainder of words once a valid prefix is found. This short-circuit behavior reduces the number of concatenations and comparisons in typical cases where the match occurs early in the list.

Using the += operator on strings leverages Python’s internal optimizations for small incremental concatenations, which keeps the overhead modest for the incremental building pattern employed here.

Imagine you have a big secret word that you want to build using blocks from a box. Each block has a smaller word written on it. You pick up the blocks one by one and stick them together in a long line.

After you glue each new block onto your line, you check how long your new creation is. If your line is exactly the same length as the secret word, you look to see if the letters match perfectly. If the letters are the same, you have finished building the secret word. If your line becomes longer than the secret word, you stop because you know there is no way to make it match anymore. If you run out of blocks before your line is the right size, then you simply cannot build the secret word.

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

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