Ransom note
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
– Count letters in magazine,
– Use them one by one for ransomNote,
– If any letter runs out → false, else → true.
Is valid anagram
If lengths of s and t are not equal → return false.
Create a frequency map for characters in s.
For each character in s, increase its count in the map.
For each character in t:
– If the character doesn’t exist in the map or its count is 0, return false.
– Otherwise, decrease its count by 1.
If all characters match and no mismatch found → return true.
Word Pattern
Given a pattern and a string s, find if s follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s. Specifically:
Each letter in pattern maps to exactly one unique word in s.
Each unique word in s maps to exactly one letter in pattern.
No two letters map to the same word, and no two words map to the same letter.
Example 1:
Input: pattern = “abba”, s = “dog cat cat dog”
Output: true
Explanation:
The bijection can be established as:'a' maps to "dog".'b' maps to "cat".
Split the input string s by spaces into an array ts.
If the length of pattern and ts are different → return false.
Create two maps:
– lastS → stores the last index where each character in pattern appeared.
– lastT → stores the last index where each corresponding word in s appeared.
Loop through each index i in pattern:
– Get the current character cp = pattern[i] and the corresponding word st = ts[i].
– Retrieve their previous indices from lastS and lastT, or -1 if they haven’t appeared before.
– If the previous indices differ, it means the mapping between pattern and words is inconsistent → return false.
– Otherwise, update both maps with the current index i.
If the loop completes without mismatches → return true.
Leetcode: 290
Isomorphic String
Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.
Example 1:
Input: s = “egg”, t = “add”
Output: true
Explanation:
The strings s and t can be made identical by:
Mapping 'e' to 'a'.
Mapping 'g' to 'd'.
Logic:
If the lengths of strings s and t are not equal → return false.
Create two maps:
– lastS → stores the last index where each character in s appeared.
– lastT → stores the last index where each corresponding character in t appeared.
Loop through each index i of the strings:
– Get the current characters cs = s[i] and ct = t[i].
– Retrieve their previous indices from lastS and lastT, or -1 if they haven’t appeared before.
– If the previous indices differ, the character mapping between s and t is inconsistent → return false.
– Otherwise, update both maps with the current index i.
If the loop completes without mismatches → return true.
Leetcode : 205
Group Anagram
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
Explanation:
There is no string in strs that can be rearranged to form "bat".
The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.
Logic:
Create an empty object map to group words by their sorted character sequence.
Loop through each string in strs:
– Sort the characters of the string alphabetically to form a key (e.g., "eat" → "aet").
– If the key doesn’t exist in map, initialize it with an empty array.
– Push the original string into the array corresponding to that key.
After processing all words, return all grouped values using Object.values(map), which gives arrays of anagram groups.
