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.
1#include <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4#include <stdlib.h>
5#include <ctype.h>
6
7#define HASH_SIZE 128
8
9unsigned int hash(const char* s) {
10 unsigned int hash = 0;
11 while (*s) {
12 hash = (hash << 5) + *s++;
13 }
14 return hash % HASH_SIZE;
15}
16
17bool wordPattern(char* pattern, char* s) {
18 char* wordMap[HASH_SIZE] = {0};
19 char* reverseMap[HASH_SIZE] = {0};
20 char word[101];
21 int wordLen = 0;
22
23 int wordIndex = 0;
24 char* p = pattern;
25 while (*p) {
26 while (*s && isspace(*s)) s++; // skip spaces
27
28 wordLen = 0;
29 while (*s && !isspace(*s)) {
30 word[wordLen++] = *s++;
31 }
32 word[wordLen] = '\0';
33
34 if (wordLen == 0) return false;
35
36 unsigned int hashIndex = hash(word);
37 if (!wordMap[*p]) {
38 // new pattern character
39 if (reverseMap[hashIndex]) {
40 if (strcmp(reverseMap[hashIndex], &*p) != 0) return false;
41 } else {
42 reverseMap[hashIndex] = &*p;
43 }
44 wordMap[*p] = strdup(word);
45 } else if (strcmp(wordMap[*p], word) != 0) {
46 return false;
47 }
48 p++;
49 }
50 return *s == '\0' && *p == '\0';
51}
52
53int main() {
54 printf("%d", wordPattern("abba", "dog cat cat dog")); // 1
55 return 0;
56}
57The solution creates two mappings using arrays, tracking which pattern character maps to each word and vice versa. During each step, the program checks if the current word and character have conflicting existing mappings.
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.
1#
This C implementation uses two arrays to track the last-occurring index in pattern and s. With words stored in an array, index comparisons determine if the words and pattern characters have been alternating in previously unseen sequences.