Introduction
This blog records my journey of solving LeetCode problems from scratch, focusing not only on coding solutions but also on the logic and basic algorithms behind them. Instead of covering every problem, I'll highlight those that are conceptually elegant or reveal interesting algorithmic ideas. Each case follows a concise three-part structure: Core Idea, Code, and Algorithm Insights & Extensions.
Case 1 – Greatest Common Divisor of Strings (LeetCode #1071)
1. Core Idea:
This problem draws inspiration from number theory.
If two strings can be concatenated in both orders (str1 + str2 == str2 + str1), it means they share a repeating pattern. The length of that pattern corresponds to the greatest common divisor (gcd(a, b) = gcd(b, a % b)) of their lengths. Otherwise, there's no common base substring, and we return an empty string.
2. Code:
class Solution(object):
def gcdOfStrings(self, str1, str2):
if str1 + str2 != str2 + str1:
return ""
if len(str1) == len(str2):
return str1
if len(str1) > len(str2):
return self.gcdOfStrings(str1[len(str2):], str2)
return self.gcdOfStrings(str1, str2[len(str1):])
3. Algorithm
- Euclidean Algorithm Analogy — gcd(a, b) = gcd(b, a % b)
The recursion mimics the Euclidean algorithm for finding the GCD of two integers:
repeatedly subtract (or in this case, slice) the shorter component from the longer until equality is reached.
Case 2 – Can Place Flowers (LeetCode #605)
1. Core Idea
The problem asks whether we can plant n new flowers in a flowerbed without violating the “no adjacent flowers” rule.
The intuitive approach is to check every position and plant a flower only when both its left and right neighbors are empty.
To simplify boundary checking (so the first and last plots don’t need special treatment), we can pad the array with zeros at both ends, imagine adding one virtual empty plot before and after the flowerbed.
2. Code:
class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
flowerbed = [0] + flowerbed + [0]
count = 0
for i in range(1, len(flowerbed) - 1):
# Check if current plot and neighbors are all empty
if flowerbed[i-1:i+2] == [0, 0, 0]:
# Plant a flower and update count
flowerbed[i] = 1
count += 1
# If enough flowers have been planted, return True
if count >= n:
return True
# Return False if not enough flowers have been planted
return False
3. Algorithm
- Greedy Filling Strategy
By surrounding the array with zeros ([0] + flowerbed + [0]), we eliminate boundary conditions at the edges. This transforms a “special-case” problem into a uniform iteration problem — a common trick in array processing.
