-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathword-pattern.js
More file actions
99 lines (79 loc) · 2.63 KB
/
word-pattern.js
File metadata and controls
99 lines (79 loc) · 2.63 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/**
* Problem: Word Pattern
* Link: https://leetcode.com/problems/word-pattern/
* Difficulty: Easy
*
* Given a pattern and a string s, find if s follows the same pattern.
*
* Example:
* Input: pattern = "abba", s = "dog cat cat dog"
* Output: true
*
* Time Complexity: O(n) where n is the number of words
* Space Complexity: O(n) for the hash maps
*/
// JavaScript Solution
function wordPattern(pattern, s) {
const words = s.split(' ');
// If lengths don't match, pattern can't match
if (pattern.length !== words.length) return false;
const patternToWord = new Map();
const wordToPattern = new Map();
for (let i = 0; i < pattern.length; i++) {
const char = pattern[i];
const word = words[i];
// Check if pattern char is already mapped
if (patternToWord.has(char)) {
if (patternToWord.get(char) !== word) return false;
} else {
patternToWord.set(char, word);
}
// Check if word is already mapped
if (wordToPattern.has(word)) {
if (wordToPattern.get(word) !== char) return false;
} else {
wordToPattern.set(word, char);
}
}
return true;
}
// Test cases
console.log(wordPattern("abba", "dog cat cat dog")); // true
console.log(wordPattern("abba", "dog cat cat fish")); // false
console.log(wordPattern("aaaa", "dog cat cat dog")); // false
module.exports = wordPattern;
/* Python Solution (commented):
def word_pattern(pattern: str, s: str) -> bool:
"""
Determines if string s follows the pattern
Args:
pattern: Pattern string (e.g., "abba")
s: String to check (e.g., "dog cat cat dog")
Returns:
True if s follows pattern, False otherwise
"""
words = s.split()
# If lengths don't match, pattern can't match
if len(pattern) != len(words):
return False
pattern_to_word = {}
word_to_pattern = {}
for char, word in zip(pattern, words):
# Check if pattern char is already mapped
if char in pattern_to_word:
if pattern_to_word[char] != word:
return False
else:
pattern_to_word[char] = word
# Check if word is already mapped
if word in word_to_pattern:
if word_to_pattern[word] != char:
return False
else:
word_to_pattern[word] = char
return True
# Test cases
print(word_pattern("abba", "dog cat cat dog")) # True
print(word_pattern("abba", "dog cat cat fish")) # False
print(word_pattern("aaaa", "dog cat cat dog")) # False
*/