How to solve the word pattern problem in Go Java algorithm

Word rules

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

Method 1: Hash table (Java)

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) != &#39; &#39;) {
                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)

Method 1: Hash table (GO)

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!