LeetCode - Easy - 290. Word Pattern

淡淡的烟草味﹌ 2022-10-28 04:55 81阅读 0赞

## Topic ##

*  Hash Table

## Description ##

[https://leetcode.com/problems/word-pattern/][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));
    	}
    	
    }

[https_leetcode.com_problems_word-pattern]: https://leetcode.com/problems/word-pattern/