Header Ad

Leetcode Word Pattern problem solution

In this Leetcode Word Pattern problem solution we have 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.

Leetcode Word Pattern problem solution


Problem solution in Python.

class Solution:
    def wordPattern(self, pattern: str, str: str) -> bool:
        unique_pattern = len(set([char for char in pattern]))
        unique_s = len(set([char for char in str.split(' ')]))
        if unique_pattern != unique_s:
            return False
        matching_elements = dict(zip([char for char in pattern],str.split(' ')))
        pattern_list = [char for char in pattern]
        result_list = list(map(matching_elements.get, pattern_list))
        if None in result_list:
            return False
        result_string = ' '.join(result_list)
        if result_string == str:
            return True
        return False



Problem solution in Java.

class Solution {
public boolean wordPattern(String pattern, String s) {

    String []arr=s.split(" ");
    if(arr.length!=pattern.length())
        return false;
    HashMap<Character,String> map=new HashMap<>();
    HashSet<String> set=new HashSet<>();
    for(int i=0;i<arr.length;i++)
    {
        char temp=pattern.charAt(i);
        if(map.containsKey(temp))
        {
            if(!map.get(temp).equals(arr[i]))
                return false;
        }
        else if(set.contains(arr[i]))
            return false;
        else
        {
            set.add(arr[i]);
            map.put(temp,arr[i]);
        }
    }
    return true;
    
}
}


Problem solution in C++.

bool wordPattern(string pattern, string str) {
        std::vector<string> words(26,"");
        std::unordered_map<string,int> wordDict;
        int start = 0;
        int end = 0;
        for(int i = 0; i < pattern.size(); ++i){
            end = start;
            while(end < str.size() && str[end] != ' ') ++end;
            std::string currWord = str.substr(start, end-start);
            if(words[pattern[i]-'a'] == ""){
                if(wordDict.find(currWord) != wordDict.end()) return false;
                words[pattern[i]-'a'] = currWord;
                wordDict[currWord] = 1;
            }else{
                if(words[pattern[i]-'a'] != currWord) {
                    return false;
                }
            }
            start = end+1;
            if(start >= str.size()){
                if(i == pattern.size()-1){
                    return true;
                }else{
                    return false;
                }
            }
        }
        return false;
    }


Problem solution in C.

bool wordPattern(char* pattern, char* str) {
  int map[26] = { 0 }, hash = 0;
  int idx = 0, j = 0;

  for (; *pattern; pattern++) {
    idx = *pattern - 'a';
    
    while (*str && *str == ' ')
      str++;
    
    hash = 0;
    while (*str && *str != ' ')
      hash = 31 * hash + *(str++);
    
    if (!hash) {
      break;
    } else if (map[idx] == 0) {
      for (j = 0; j < 26; j++) {
        if (j != idx && map[j] == hash)
          return false;
      }
      map[idx] = hash;
    } else if (map[idx] != hash) {
      return false;
    }
  }

  while (*str && *str == ' ')
    str++;

  return !*pattern && !*str;
}


Post a Comment

0 Comments