Day 50.2.txt

290. 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.



class Solution {
    public boolean wordPattern(String p, String s) {
        List<String> nm=new ArrayList<>();
        int i,j=0;
        for(i=1;i<s.length();i++)
        {
            if(s.charAt(i)==' ')
            {
                nm.add(s.substring(j,i));
                j=i+1;
            }
        }
        nm.add(s.substring(j,i));
        if(nm.size()!=p.length())
            return false;
        HashMap<String,Character> kk=new HashMap<>();
        for(i=0;i<nm.size();i++)
        {
            if(kk.containsKey(nm.get(i)))
            {
                if(kk.get(nm.get(i))!=p.charAt(i))
                    return false;
            }
            if(kk.containsValue(p.charAt(i))&&!kk.containsKey(nm.get(i)))
                return false;
            else
                kk.put(nm.get(i),p.charAt(i));
        }
        return true;
    }
}