Word Pattern II

Leave a comment

February 13, 2017 by oneOokay

Given a pattern and a string str, find if str 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 substring in str.

Examples:

  1. pattern = "abab", str = "redblueredblue" should return true.
  2. pattern = "aaaa", str = "asdasdasdasd" should return true.
  3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:
You may assume both pattern and str contains only lowercase letters.


挺典型的应该想到Backtracking, 因为要确认每一个pattern里面的char所代表的substring.

就看一下吧,很久没写backtracking了….

这题的backtracking是对一个map进行加入和移除.

  • str.startsWith(String p, int startIndex) return boolean:str在index=startIndex的地方开始是否以p为prefix
  • str.startsWith(String p) return boolean: str是否以p为prefix
public boolean wordPatternMatch(String pattern, String str) {
        Map<Character, String> map = new HashMap<Character, String>();
        return helper(map, str, 0, pattern, 0);
    }
    
    public boolean helper(Map<Character, String> map, String str, int sIndex, String pattern, int pIndex){
        if (sIndex == str.length() && pIndex == pattern.length()) return true;
        if (sIndex == str.length() || pIndex == pattern.length()) return false;
        
        char c = pattern.charAt(pIndex);
        if (map.containsKey(c)){
            String s = map.get(c);
            
            if(!str.startsWith(s, sIndex)) return false;
            return helper(map, str, sIndex + s.length(), pattern, pIndex + 1);
        }
        //当map里面不存在c的时候,要对一个新的c pattern进行backtracking判断
        for (int i = sIndex; i < str.length(); i ++){
            String s = str.substring(sIndex, i + 1);
            if (map.containsValue(s)) continue;
            map.put(c, s);
            if (helper(map, str, i + 1, pattern, pIndex + 1)) return true;
            
            map.remove(c);
        }
        return false;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: