Problems Solved:
- #242 Valid Anagram
- #49 Group Anagrams
This is a followβup to my daily series (Day 1: Two Sum & Contains Duplicate). Today I focused on string hashing/sorting patterns and pushed both Python and C++ solutions.
π‘ What I Learned
Today, I focused on practicing string manipulation and hashing techniques in both Python and C++.
Key takeaways:
-
Python: Learned how to leverage
sorted()
anddefaultdict
for concise grouping of anagrams. -
C++: Reinforced understanding of
unordered_map
for hashing and the trade-off between sorting vs. counting keys for efficiency. - Realized that mutating containers while iterating (in Python) or mishandling return types (in C++) are common pitfalls to watch out for.
π§© #242 β Valid Anagram
Python (Sorting)
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
new_s = ''.join(sorted(s))
new_t = ''.join(sorted(t))
return new_s == new_t
Why it works: anagrams have identical sorted representations.
Time: O(k log k)
per string.
Space: O(k)
due to intermediate copies.
C++ (Sorting)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};
Alternative (when alphabet is known, e.g., lowercase aβz): count array of size 26 β
O(k)
.
π§© #49 β Group Anagrams
Python (Sorted Key)
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for word in strs:
key = ''.join(sorted(word)) # canonical form
groups[key].append(word)
return list(groups.values())
Time: O(n Β· k log k)
Space: O(n Β· k)
C++ (Sorted Key)
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> groups;
groups.reserve(strs.size());
for (string word : strs) {
string key = word;
sort(key.begin(), key.end());
groups[key].push_back(move(word));
}
vector<vector<string>> result;
result.reserve(groups.size());
for (auto &kv : groups) {
result.push_back(move(kv.second));
}
return result;
}
};
Bonus: O(n Β· k)
CountingβKey (idea)
- Build a frequency vector of 26 counts for each word and use it (as a tuple or joined string) as the map key.
- Avoids sorting cost β better for long strings.
Pseudoβkey example (C++ idea): key = "#c0#c1#c2...#c25"
from the 26 counters.
πΈ Achievements
- Valid Anagram (Python & C++):
- Group Anagrams (Python & C++):
π¦ Complexity Recap
-
Valid Anagram:
O(k log k)
(sort) orO(k)
(counts) -
Group Anagrams:
O(n Β· k log k)
(sort key) orO(n Β· k)
(count key)
π£ Join the Journey
Iβm posting daily, solving each task in both Python and C++, and writing down what actually matters (patterns, mistakes, and tradeβoffs). Follow along if youβre into algorithms and practical performance.
Links
- LinkedIn: https://www.linkedin.com/in/ertugrul-mutlu
- GitHub Series: https://github.com/Ertugrulmutlu/leetcode-series
Top comments (0)