Detailed explanation of the word rules examples of Go Java algorithm

Word rules

Given a pattern  and a string s , determine whether s follows the same rule.

The following here refers to the exact match. For example, there is a corresponding law of bidirectional connection between each letter in pattern and each non-empty word in string s.

• Example 1:

Enter: pattern = "abba", s = "dog cat cat dog"

Output: true

• Example 2:

Enter: pattern = "abba", s = "dog cat cat fish"

Output: false

• Example 3:

Enter: pattern = "aaaa", s = "dog cat cat dog"

Output: false

hint:

1 <= <= 300

pattern only contains lowercase English letters

1 <= <= 3000

s contains only lowercase English letters and ''

s does not contain any leading or trailing pair spaces

Each word in s is separated by a single space

Method 1: Hash table (Java)

In this question, we need to judge whether the characters and string correspond exactly one by one. That is, any character corresponds to a unique string, and any character string is only corresponded to by a unique character. In set theory, this relationship is called "double shot".

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 constantly update the hash table. If a conflict occurs, it means that the given input does not satisfy the bijection relationship.

The question essentially lets us judge whether the characters in str correspond to the characters in pattern one by one.

That is to say, the same characters in pattern should also be the same in str, and different characters should also be the same in str

We can record the first occurrence of each character in the pattern through a dictionary, that is, dict[x]=(x). Then we iterate through each letter in the pattern,

Note i as the index of the current traversal

Then dict[pattern[i]] is the last 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> ch2str = new HashMap<Character, String>();
        int m = ();
        int i = 0;
        for (int p = 0; p < (); ++p) {
            char ch = (p);
            if (i >= m) {
                return false;
            }
            int j = i;
            while (j < m && (j) != ' ') {
                j++;
            }
            String tmp = (i, j);
            if ((tmp) && (tmp) != ch) {
                return false;
            }
            if ((ch) && !((ch))) {
                return false;
            }
            (tmp, ch);
            (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 methods and ideas have been expressed in the above article. For details, please refer to the above article.

Specific methods:

pattern = "abba", converted to 0110

str = "dog cat cat dog", convert to 0110

func wordPattern(pattern string, str string) bool {
    p := (pattern,"")
    s := (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 += (pMap[v])
        }else{
            pString += (pNum)
            pMap[v] = pNum
            pNum++
        }
    }
    for _,v := range s {
        if _,ok := sMap[v];ok{
            sString += (sMap[v])
        }else{
            sString += (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 a detailed explanation of the word rules examples of Go Java algorithm. For more information about the word rules of Go Java algorithm, please pay attention to my other related articles!