LeetCode - Easy - 290. Word Pattern-蒲公英云

LeetCode - Easy - 290. Word Pattern

Topic

Hash Table

Description

https://leetcode.com/problems/word-pattern/

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in 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

Example 4:

Input: pattern = "abba", s = "dog dog dog dog"
Output: false

Constraints:

1 <= pattern.length <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lower-case English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

Analysis

双向映射。

注意，Java包装整型的比较问题。

Submission

import java.util.HashMap;
import java.util.Objects;
public class WordPattern { 
    // 方法一：我写的，双向映射
    public boolean wordPattern1(String pattern, String s) { 
        // 双向映射
        HashMap<Character, Integer> aMap = new HashMap<>();
        HashMap<String, Integer> bMap = new HashMap<>();
        String[] words = s.split(" ");
        if (pattern.length() != words.length)
            return false;
        int count = 0;// 这可省略，改用下面循环体的i变量
        for (int i = 0; i < pattern.length(); i++) { 
            Character cr = pattern.charAt(i);
            Integer id1 = aMap.get(cr);
            Integer id2 = bMap.get(words[i]);
            if (id1 == null && id2 == null) { 
                aMap.put(cr, count);
                bMap.put(words[i], count++);
            } else { 
                if (id1 != id2)// 这要改成Objects.equals()
                    return false;
            }
        }
        return true;
    }
    // 方法二：双向映射，比方法一更简洁
    public boolean wordPattern2(String pattern, String s) { 
        String[] words = s.split(" ");
        if (words.length != pattern.length())
            return false;
        HashMap<Object, Object> index = new HashMap<>();//Object类型key即可放Character，亦可放String，我没想到
        for (Integer i = 0; i < words.length; ++i)
            if (!Objects.equals(index.put(pattern.charAt(i), i), //
                    index.put(words[i], i)))
                return false;
        return true;
    }
}

Test

import static org.junit.Assert.*;
import java.util.Objects;
import org.junit.Test;
public class WordPatternTest { 
    @Test
    public void test() { 
        WordPattern obj = new WordPattern();
        assertTrue(obj.wordPattern1("abba", "dog cat cat dog"));
        assertFalse(obj.wordPattern1("abba", "dog cat cat fish"));
        assertFalse(obj.wordPattern1("aaaa", "dog cat cat dog"));
        assertFalse(obj.wordPattern1("abba", "dog dog dog dog"));
        assertTrue(obj.wordPattern2("abba", "dog cat cat dog"));
        assertFalse(obj.wordPattern2("abba", "dog cat cat fish"));
        assertFalse(obj.wordPattern2("aaaa", "dog cat cat dog"));
        assertFalse(obj.wordPattern2("abba", "dog dog dog dog"));
    }
    @Test
    public void testEquals() { 
        //== 与 !=运用在Integer包装类的比较的局限性
        //包装类最好用Objects.equals()
        int i = 127;
        Integer a = i;
        Integer b = i;
        assertTrue(a == b);
        assertTrue(Objects.equals(a, b));
        i = 128;
        a = i;
        b = i;
        assertFalse(a == b);
        assertTrue(Objects.equals(a, b));
    }
}