Leetcode Study Day 20

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.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
 

Constraints:

1 <= pattern.length <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lowercase English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

My solution

Let me explain my solution in the code:

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        // create two maps to store the mapping between characters and words
        unordered_map <char, string> charMatch;
        unordered_map <string, char> stringMatch;
        // create a pointer to point to the pattern
        int patternPointer = 0;
        string word = "";
        // create a counter to count the number of words
        int wordCounter = 0;
        for (int i = 0; i <= s.size(); i++){
            // if we reach the end of the string or we reach a space
            if (s[i] == ' ' || i == s.size()){
                auto find = charMatch.find(pattern[patternPointer]);
                auto findS = stringMatch.find(word);
                // if we don't find the element in the map
                if (find == charMatch.end() && findS == stringMatch.end()){
                    // insert the element into the map
                    charMatch[pattern[patternPointer]] = word;
                    stringMatch[word] = pattern[patternPointer];
                    word = "";
                    patternPointer ++;
                    wordCounter ++;
                }
                else{
                    // if we find the element in the map but the mapping is not correct
                    if (charMatch[pattern[patternPointer]] != word || stringMatch[word] != pattern[patternPointer]) 
                        return false;
                    else{
                        word = "";
                        patternPointer ++;
                        wordCounter ++;
                    }
                }
            }
            else
                word += s[i];
        }
        // if the number of words is not equal to the number of characters
        if (wordCounter != pattern.size())
            return false;
        return true;
    }
};

Valid Anagram

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.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
Example 2:

Input: s = "rat", t = "car"
Output: false
 

Constraints:

1 <= s.length, t.length <= 5 * 104
s and t consist of lowercase English letters.

My solution

Let me explain my solution in the code:

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map <char, int> wordCount;
        // count the number of characters in s
        for (int i = 0; i < s.size(); i++){
            wordCount[s[i]] ++;
        }
        // check if the characters in t are in s
        for (int j = 0; j < t.size(); j++){
            // if the character is not in s or the number of the character in t is more than in s
            if(wordCount[t[j]] == 0)
                return false;
            // if the character is in s
            else
                wordCount[t[j]]--;
        }
        // check if there are any characters left in s
        for (int i = 0; i < s.size(); i++){
            // if there are characters left in s
            if (wordCount[s[i]] != 0)
                return false;
        }
        // if there are no characters left in s
        return true;
    }
};