Python 1528.py
class Solution:
def restoreString(self, s: str, indices: List[int]) -> str:
result = [ None ] * len(s)
for c, i in zip(s, indices):
result[i] = c
return "".join(result)
Difficulty
and has an acceptance rate of about 86% (500k+ submissions).
Typical patterns to solve this problem:
- Array
- String
AI Disclaimer
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.
Code Walkthrough
Overview
The provided implementation defines a class Solution with a single method restoreString. The method receives a string s and a list of integer positions indices. Its purpose is to reconstruct a new string where each character from s is placed at the index specified by the corresponding entry in indices. The algorithm builds an intermediate list to hold characters at their target positions and finally concatenates the list into the resulting string.
Key Steps and Corresponding Code
The core logic can be broken down into three distinct operations.
Allocation of a Fixed-size Container
result = [ None ] * len(s)
A list named result is created with a length equal to the input string. Each slot is initially filled with None. This pre-allocation guarantees constant-time access for later assignments and eliminates the need for dynamic resizing during the reconstruction phase.
Placement of Characters According to the Mapping
for c, i in zip(s, indices):
result[i] = c
The zip function pairs each character c from the source string with its target index i from the indices list. Inside the loop, the character is stored directly at position i in the result list. Because the list was pre-sized, the assignment operation runs in constant time for each pair.
Conversion of the Container to the Final String
return "".join(result)
After all characters have been positioned, the list is transformed into a single string using the join method. This step concatenates the elements of result in order, producing the restored string that the method returns.
Edge Cases Handled by the Implementation
The algorithm gracefully manages several boundary conditions without additional checks.
When the input string is empty, len(s) evaluates to zero, resulting in an empty list result. The subsequent loop does not execute because zip yields no pairs, and the final join on an empty list returns an empty string. Thus, an empty input yields an empty output as expected.
If the indices list contains the identity permutation (i.e., each index matches its position), the loop writes each character back to its original slot. The final join reproduces the original string, confirming that the method correctly handles the no-reordering scenario.
When indices provides a reverse ordering, the loop still assigns each character to its new location, and the join produces the reversed string. This demonstrates that the method works for any bijective mapping of positions.
The code also tolerates duplicate characters in the source string because placement is driven solely by the index values, not by character uniqueness. Consequently, strings with repeated symbols are reconstructed accurately.
Performance Optimizations Observed
The implementation exhibits several deliberate choices that contribute to efficient execution.
Pre-allocating the result list avoids the overhead associated with repeatedly appending to a dynamic array. By knowing the exact size upfront, the algorithm sidesteps potential reallocations and copying that would occur with incremental growth.
Using zip to iterate over both s and indices in a single pass eliminates the need for separate indexing variables or multiple loops. This tight coupling reduces interpreter overhead and keeps the iteration count minimal-exactly the length of the input string.
Assigning characters directly into the list by index leverages Python’s O(1) list item assignment. No intermediate data structures are created during the placement phase, which conserves memory and speeds up the operation.
Finally, the join method is the idiomatic way to concatenate a sequence of strings in Python. It performs the concatenation in a single pass, allocating the final string only once. This is markedly faster than repeatedly using the + operator, which would generate intermediate strings and increase memory churn.
ELI5 - Simplified Explanation
Imagine you have a row of empty boxes laid out on a table, and each box has a special number written on it. You also have a handful of colorful letter stickers that are currently all mixed up. Each sticker has a letter on the front and a secret number on the back that tells you exactly which box it belongs in.
To fix the mess, you pick up a sticker, look at the secret number on the back, and walk over to the box with that same number. You carefully place the sticker inside its matching home. You keep doing this for every single sticker you have until every box is filled with the right letter. Once all the boxes are tucked away in their correct spots, you look at them from left to right and read the letters to see the new word you have built.
Code Quality
Complexity Analysis
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
Other Solutions
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++ | Python | Java | TS | ||||||
| WalkCCC | C++ | ||||||||||
| leetcode.ca | C++ | Python | Java | JS | Go | Rust | TS | ||||
| Progiez | C++ | Python | Java | ||||||||
| github | black-shadows | C++ | |||||||||
| chandansgowda | Python | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JS | ||||||||||
| fartem | Ruby | ||||||||||
| FelixFan1122 | Java | ||||||||||
| fsq | C++ | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JS | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| Krazune | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| MacJim | C++ | ||||||||||
| muhammadfarhankt | Go | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| varunu28 | Java | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++ | ||||||||||
| leetcode.ca | C++, Go, Java, JavaScript, Python, Rust, TypeScript | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| chandansgowda | Python | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JavaScript | ||||||||||
| fartem | Ruby | ||||||||||
| FelixFan1122 | Java | ||||||||||
| fsq | C++ | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| Krazune | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| MacJim | C++ | ||||||||||
| muhammadfarhankt | Go | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| varunu28 | Java | ||||||||||
| YuriSpiridonov | Python |
Videos
Solved On The Same Day
- problem 1480: Running Sum of 1d Array
- problem 1773: Count Items Matching a Rule
- problem 1816: Truncate Sentence
- problem 1832: Check if the Sentence Is Pangram
- problem 1859: Sorting the Sentence
- problem 2114: Maximum Number of Words Found in Sentences
- problem 2828: Check if a String Is an Acronym of Words
- problem 1329: Sort the Matrix Diagonally
- problem 1551: Minimum Operations to Make Array Equal
Extra
- 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