Home >Java >javaTutorial >How to solve the word pattern problem in Go Java algorithm
Given a pattern pattern and a string s, determine whether s follows the same rule.
Follow here refers to an exact match. For example, there is a two-way connection correspondence rule between each letter in pattern and each non-empty word in string 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
Prompt:
1 <= pattern.length < = 300
pattern Contains only lowercase English letters
1 <= s.length <= 3000
s Contains only lowercase English letters and ' '
s do not contain any leading or trailing pairs of spaces
s where each word is separated by a single space
In this question, we need to determine whether there is an exact one-to-one correspondence between characters and strings. That is, any character corresponds to a unique string, and any string is corresponded to only one character. In set theory, this relationship is called a "bijection".
To solve this problem, we can use a hash table to record the string corresponding to each character and the characters corresponding to each string. Then we enumerate the pairing process of each pair of characters and strings and continuously update the hash table. If a conflict occurs, it means that the given input does not satisfy the bijection relationship.
The question essentially asks us to determine whether the characters in str correspond to the characters in pattern one-to-one
That is to say, the same characters in pattern should also be the same in str, and different characters The characters should also be different in str
We can record the first occurrence position of each character in pattern through a dictionary, that is, dict[x]=pattern.index(x). Then we traverse each letter in the pattern,
Remember i as the index of the current traversal
Then dict[pattern[i]] is the previous index of the character pattern[i] in pattern
Determine whether the letters corresponding to the two indexes in str are the same. If they are different, return False
class Solution { public boolean wordPattern(String pattern, String str) { Map<String, Character> str2ch = new HashMap<String, Character>(); Map<Character, String> ch3str = new HashMap<Character, String>(); int m = str.length(); int i = 0; for (int p = 0; p < pattern.length(); ++p) { char ch = pattern.charAt(p); if (i >= m) { return false; } int j = i; while (j < m && str.charAt(j) != ' ') { j++; } String tmp = str.substring(i, j); if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) { return false; } if (ch3str.containsKey(ch) && !tmp.equals(ch3str.get(ch))) { return false; } str2ch.put(tmp, ch); ch3str.put(ch, tmp); i = j + 1; } return i >= m; } }
Time complexity: O (n m)
Space complexity: O (n m)
The specific method ideas have been stated above, please see the above content for details
Specific method:
pattern = "abba", converted to 0110
str = "dog cat cat dog", converted to 0110
func wordPattern(pattern string, str string) bool { p := strings.Split(pattern,"") s := strings.Split(str," ") if len(p) != len(s) { return false } pNum,sNum := 0,0 pString,sString := "","" pMap := map[string]int{} sMap := map[string]int{} for _,v := range p { if _,ok := pMap[v];ok{ pString += strconv.Itoa(pMap[v]) }else{ pString += strconv.Itoa(pNum) pMap[v] = pNum pNum++ } } for _,v := range s { if _,ok := sMap[v];ok{ sString += strconv.Itoa(sMap[v]) }else{ sString += strconv.Itoa(sNum) sMap[v] = sNum sNum++ } } if pString == sString { return true } return false }
Time complexity: O(n m)
Space complexity: O(n m)
The above is the detailed content of How to solve the word pattern problem in Go Java algorithm. For more information, please follow other related articles on the PHP Chinese website!