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.

Functional Implementation of WordPattern

Java

  public class WordPattern {

      public boolean wordPattern(String pattern, String str) {
          String[] arr= str.split(" ");
          HashMap<Character, String> map = new HashMap<Character, String>();
          if(arr.length!= pattern.length())
              return false;
          for(int i=0; i<arr.length; i++){
              char c = pattern.charAt(i);
              if(map.containsKey(c)){
                  if(!map.get(c).equals(arr[i]))
                      return false;
              }else{
                  if(map.containsValue(arr[i]))
                      return false;
                  map.put(c, arr[i]);
              }    
          }
          return true;
      }
  }

See also :

Linear Search
Jump Search
Binary Search
Exponential Search
Interpolation Search