Sponsored
Sponsored
This approach uses two hash maps (dictionaries) to establish bijective mappings between characters in the pattern and words in the string. One map tracks the character to word mapping, while the other tracks word to character mapping. During iteration, we update or check both maps to ensure the bijection property holds.
Time Complexity: O(n + m), where n is the length of the pattern and m is the length of the string. Each space-separated word in s is checked at least once.
Space Complexity: O(n + m) for storing the mapping of characters to words and words to characters.
1using System;
2using System.Collections.Generic;
3
4class Solution {
5 public bool WordPattern(string pattern, string s) {
6 string[] words = s.Split(' ');
7 if (pattern.Length != words.Length) return false;
8
9 Dictionary<char, string> charToWord = new Dictionary<char, string>();
10 Dictionary<string, char> wordToChar = new Dictionary<string, char>();
11
12 for (int i = 0; i < pattern.Length; i++) {
13 char c = pattern[i];
14 string word = words[i];
15
16 if (charToWord.ContainsKey(c) && charToWord[c] != word) return false;
17 if (wordToChar.ContainsKey(word) && wordToChar[word] != c) return false;
18
19 charToWord[c] = word;
20 wordToChar[word] = c;
21 }
22
23 return true;
24 }
25
26 static void Main() {
27 Solution sol = new Solution();
28 Console.WriteLine(sol.WordPattern("abba", "dog cat cat dog"));
29 }
30}
31In this C# solution, the Dictionary class manages mappings between characters and words, similar to the HashMaps in the Java solution. The logic maintains checks at each step to ensure accurate bidirectional mapping.
The index mapping approach ensures that the last seen indexes of each character in the pattern and each word from s match. By tracking their last occurrences, you can simplify identifying mismatched patterns in linear time.
Time Complexity: O(n + m), where n is the pattern length and m is sā length.
Space Complexity: O(n + m) concerning the arrays holding the last occurring indices.
1using System.Collections.Generic;
class Solution {
public bool WordPattern(string pattern, string s) {
string[] words = s.Split(' ');
if (pattern.Length != words.Length) return false;
Dictionary<object, int> indexMap = new Dictionary<object, int>();
for (int i = 0; i < pattern.Length; i++) {
if (!indexMap.TryAdd(pattern[i], i) && indexMap[pattern[i]] != i)
return false;
if (!indexMap.TryAdd(words[i], i) && indexMap[words[i]] != i)
return false;
}
return true;
}
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.WordPattern("abba", "dog cat cat dog"));
}
}
The C# solution employs a dynamic dictionary to conserve the indexes of each character and word. Utilizing TryAdd allows the handling of previous mappings efficiently, checking equality through index matching in parallel.