Leetcode 290. Word Pattern

Problem Explanation

The problem is asking you to implement a function that checks if a given string follows a specific pattern. Here, following a specific pattern means that there is a one-to-one correspondence between the characters of the pattern and the words in the string. Each character in the pattern is mapped to a unique word and vice versa. The string constitutes of lowercase letters separated by a space and the pattern contains lowercase letters.

For instance, let's consider these examples:

Example 1: Input: pattern = "abba", str = "dog cat cat dog" Output: true In this example, 'a' corresponds to 'dog' and 'b' corresponds to 'cat'. And, vice versa, 'dog' corresponds to 'a' and 'cat' corresponds to 'b'. Thus, the string follows the pattern.

Example 2: Input:pattern = "abba", str = "dog cat cat fish" Output: false In this example, 'a' corresponds to 'dog' and 'b' corresponds to 'cat'. However, the word 'fish' doesn't correspond to 'a'. Therefore, the string does not follow the pattern.

Approach Explanation

The solution approach loops through each character of the pattern and each word of the string. It uses two mappings— one for characters to words and the other for words to characters. At each index, it checks whether a character maps to a word and whether a word maps to a character. If the mapping doesn't match, it returns false. If the loop finishes without returning false and if the number of words matches with the number of characters in the pattern, it returns true.

This solution uses two important data structures:

1. An array to keep track of mapping from a character to an index.
2. An unordered map to keep track of mapping from a word to an index.

The reason for using an unordered map is its average constant time complexity for search, insert and delete operations.

Let's take an example: pattern = "abba", str = "dog cat cat dog".

• In the first iteration, i is 0, pattern[i] is 'a', and word is 'dog'. The function checks if the mappings are correct. In this case, they are.
• Then it sets charToIndex['a'] and stringToIndex['dog'] to i + 1 which is 1.
• In the second and third iterations, similar steps are repeated for 'b' and 'cat'.
• In the final iteration, 'a' and 'dog' match with the original mapping (i.e., 1), thus returning true.

C++ Solution

1
2c++
3class Solution {
4 public:
5  bool wordPattern(string pattern, string str) {
6    const int n = pattern.length();
7    istringstream iss(str);
8    vector<int> charToIndex(128);
9    unordered_map<string, int> stringToIndex;
10
11    int i = 0;
12    for (string word; iss >> word; ++i) {
13      if (i == n)  // Check if pattern is long enough for the string
14        return false;
15      if (charToIndex[pattern[i]] != stringToIndex[word])  // Check if mappings are correct
16        return false;
17      charToIndex[pattern[i]] = i + 1;  // Update mappings with current index
18      stringToIndex[word] = i + 1;
19    }
20
21    return i == n;  // Check if string is long enough for the pattern
22  }
23};

(make sure to fill the other solutions for python, java, javascript, c# ...)## Python Solution

1
2python
3class Solution:
4    def wordPattern(self, pattern: str, str: str) -> bool:
5        words = str.split()  # split string into words
6        if len(pattern) != len(words):  # Check if pattern is long enough for the string
7            return False
8            
9        char_to_index = {}
10        word_to_index = {}
11        
12        for i in range(len(pattern)):
13            # Check if mappings are correct
14            if char_to_index.get(pattern[i]) != word_to_index.get(words[i]):
15                return False
16            # Update mappings with current index
17            char_to_index[pattern[i]] = word_to_index[words[i]] = i + 1
18            
19        return True

Java Solution

1
2java
3public class Solution {
4    public boolean wordPattern(String pattern, String str) {
5        String[] words = str.split(" ");
6        if (pattern.length() != words.length) // Check if pattern is long enough for the string
7            return false;
8            
9        Map index = new HashMap();
10        for (Integer i=0; i < words.length; i++)
11            // Check if mappings are correct
12            if (index.put(pattern.charAt(i), i) != index.put(words[i], i))
13                return false;
14        return true;
15    }
16}

JavaScript Solution

1
2javascript
3var wordPattern = function(pattern, str) {
4    var words = str.split(' ');
5    if (pattern.length != words.length) // Check if pattern is long enough for the string
6        return false;
7        
8    var charToIndex = {};
9    var wordToIndex = {};
10    
11    for (var i = 0; i < pattern.length; i++) {
12        // Check if mappings are correct
13        if (charToIndex[pattern[i]] != wordToIndex[words[i]])
14            return false;
15        // Update mappings with current index
16        charToIndex[pattern[i]] = wordToIndex[words[i]] = i + 1;
17    }
18    
19    return true;
20}

C# Solution

1
2csharp
3public class Solution {
4    public bool WordPattern(string pattern, string str) {
5        var words = str.Split(' ');
6        var charToIndex = new Dictionary<char, int>();
7        var wordToIndex = new Dictionary<string, int>();
8        
9        if (pattern.Length != words.Length)  // Check if pattern is long enough for the string
10            return false;
11        
12        for (var i = 0; i < pattern.Length; i++) {
13            if (charToIndex.TryAdd(pattern[i], i + 1) != wordToIndex.TryAdd(words[i], i + 1)) // Check if mappings are correct
14                return false;
15        }
16        
17        return true;
18    }
19}

This code checks if each corresponding pair in pattern and str have the exact same pattern and then returns the final result. It uses dictionaries to track the previous occurrences of each character and word, and checks if they have the same pattern. If any pair violates the pattern, the function returns false. Otherwise it continues to the next pair. This solution runs in O(n) time where n is the length of the pattern, and uses O(n) extra space.