Search for a command to run...
Three C++ solutions for solving Leetcode 242. Valid Anagram. An anagram is a word formed by rearranging the letters of another word.
Hi! My name is Nhut Nguyen. I am a software engineer and a writer in Copenhagen, Denmark.
Learn more about me at nhutnguyen.com
No comments yet. Be the first to comment.
A simple example of using C++ switch
Two dynamic programming techniques to solve Leetcode 120. Triangle. One has space complexity O(n^2). The other is O(n).
An example of using a sliding window approach and an unordered map to track character positions
A simple C++ solution to Leetcode 1695. Maximum Erasure Value using a sliding window approach and prefix sums.
Strategies to avoid them will help you excel in your following technical interview
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false
1 <= s.length, t.length <= 5 * 10^4.
s and t consist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
s and t into a sorted string#include <iostream>
#include <algorithm>
using namespace std;
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
int main() {
cout << isAnagram("anagram", "nagaram") << endl;
cout << isAnagram("rat", "car") << endl;
}
Output:
1
0
Runtime: O(NlogN), where N = s.length.
Extra space: O(1).
#include <iostream>
using namespace std;
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
int alphabet[26];
for (int i = 0; i < 26; i++) {
alphabet[i] = 0;
}
for (char& c : s) {
alphabet[c - 'a']++;
}
for (char& c : t) {
alphabet[c - 'a']--;
if (alphabet[c - 'a'] < 0) {
return false;
}
}
return true;
}
int main() {
cout << isAnagram("anagram", "nagaram") << endl;
cout << isAnagram("rat", "car") << endl;
}
Output:
1
0
Runtime: O(N), where N = s.length.
Extra space: O(1).
In the solutions above, the array alphabet represents 26 letters 'a' to 'z'. You can generalize to allow it contains any character by using a map.
#include <iostream>
#include <unordered_map>
using namespace std;
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
unordered_map<char, int> alphabet;
for (char& c : s) {
alphabet[c]++;
}
for (char& c : t) {
alphabet[c]--;
if (alphabet[c] < 0) {
return false;
}
}
return true;
}
int main() {
cout << isAnagram("anagæam", "nagaæam") << endl;
cout << isAnagram("rat", "car") << endl;
}
Output:
1
0
Runtime: O(N), where N = s.length.
Extra space: O(1).
An array of 26 integers can represent the English alphabet.
Counting the appearances can help identify if a word is a permutation of another.
You can use a map to count the appearances of the letters of a word.
Thanks for reading! Get my book "10 Classic Coding Challenges" for FREE.