CareerCup

A good DFS problem. Need to set 2 pointers, one in the pattern, and one in the string. Additionally, maintain a map to keep track of the mapping between a pattern letter and a substring.

bool isMatch(string str, int iStr, string ptn, int iPtn, unordered_map<char, string> &hmap){
    if(iStr == str.size() && iPtn == ptn.size()) return true;
    if(iStr == str.size() || iPtn == ptn.size()) return false;
    char c = ptn[iPtn];
    if(hmap.find(c)!=hmap.end()){
        string toMatch = hmap[c];
        for (int i = 0; i < toMatch.size(); i++) {
            if (iStr >= str.size() || str[iStr] != toMatch[i])
                return false;
            istr++;
        }
        return isMatch(str, istr, ptn, iPtn+1, hmap);
    }
    //try all possiblities
    bool flag = false;
    for (int i = iStr; i < str.size(); i++){
        hash[c] = str.substr(iStr, i - iStr + 1);
        flag |= isMatch(str, i + 1, ptn, iPtn + 1, hmap);
        hmap.erase(c);
        if(flag) return true;
    }
    return false;
}

bool isMatch(string str, string ptn){
    if(str.size()<ptn.size()) return false;
    if(ptn.empty()) return str.empty()? true : false;
    if(ptn.size()==1) return  str.size()>1? true : false;
    unordered_map<char, string> hmap;
    return isMatch(str, 0, ptn, 0, hmap);
}

Shouldn't 1) return 0? wouldn't the pattern for "abba" be "redbluebluered"?

say pattern is abbab [2 a's and 3 b's] and string = redblueblueredblue [18 chars]
Let number of chars in 'a' = x and 'b' = y

2x + 3y = 18
find all possibilities of x and y,
here it came : x = 3 and y = 4

Loop over all possibilities of x and y
Check in one more loop if string is following that pattern or not

It is easy if using regular expressions is allowed.

Just replace the first occurrences of each letter in the pattern with "(.+)" .
The subsequent occurrences will be replaced with \x, where x is the number of unique letters in the pattern the occur before that character.

So abba become "(.+)(.+)\\2\\1"

Then use the resulting regular expression to match the input string.

Below is a C++ implementation:

#include <iostream>
#include <regex>
#include <string>
using namespace std;


bool match(string input, string pattern) {
    vector<int> counts = vector<int>(26, 0);
    string regexStr;
    int uniqueCount = 0;
    for (auto c : pattern) {
        if(counts[c - 'a'] == 0) {
            regexStr += "(.+)";
            counts[c - 'a'] = ++uniqueCount;
        } else {
            regexStr += ("\\" + to_string(counts[c - 'a']));
        }
    }
    return regex_match(input.begin(), input.end(), regex(regexStr));
}


int main() {
	string input = "thequickthequickquick";
    string pattern = "ababb";
    if(match(input,pattern)) {
		cout << "Match" << endl;
	} else {
        cout << "NO match";
    }
	return 0;
}

If patterns are limited to only a and b there is an O(n) solution. That's because you need to iterate the String just once, and choose only where the first word will end.
That's because the size of the word that represents 'a' (the first word) will determine the size of the word that represent 'b' (think of it as equation in 2 variables, where a size is determined and the size of the String is also determined)

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class PatternMatch {
 
 public static void main(String[] args) {
  System.out.println(checkPattern("abba","redbluebluered"));
  System.out.println(checkPattern("aaaa","asdasdasdasd"));
  System.out.println(checkPattern("aabb","xyzabcxzyabc"));
 }
 
 public static byte checkPattern(String patternString, String input) {
  StringBuffer patternBuffer = new StringBuffer();
  
  /* check input and pattern strings */
  if (patternString == null || input == null) {
   throw new IllegalArgumentException();
  }
  
  /* pattern character array */
  List<Character> chars = new ArrayList<Character>();
  for (char c : patternString.toCharArray()) {
   
   if (!chars.contains(c)) {
    /* new character found, append new group */
    patternBuffer.append("(.+)");
    chars.add(c);
   } else {
    /* looking for unique sequence by number */
    patternBuffer.append("\\")
     .append(chars.indexOf(c)+1);
   }
  }
  
  /* compiling pattern and checking input string */
  Pattern pattern = Pattern.compile(patternBuffer.toString());
  Matcher matcher = pattern.matcher(input);
  if (matcher.find()) {
   return 1;
  }
  
  return 0;
 }
}

Well, just from the top of my mind - if you have a pattern which involved only the characters 'a' and 'b' then you need one index - where the word which associate with a ends (and resulting from that - where b begins).. So I would try all the combination to that index (from 0 to str.length) and then create a temp str from that combination, and then check (str.equals(temp str)) - if it's true - return true. if not return true and finish - return false.

If patterns are limited to only a and b, your solution is O(n^2). If however you can have d elements in the pattern, it would be O(n^d).

This question requires some knowledge about the input alphabet. Who's to say xyzabc isn't just one iteration of the pattern?

please clarify the question.
1) do exactly three consecutive letters map to one alphabet in the pattern
2) will the input pattern have only 2 alphabets ?

if we go by the examples then it is a very simple problem

Other brute force solution would be to check input String against all possible lengths of a and b.
Depending on the pattern you can always find out what the lengths of b might be if a has length x, so in 1st example you'll just have to check against cases a has length in (0, N/2) - if 0 length is possible. The complexity would be O(N^2).

would be a lot easier if the string was separated by spaces or commas. then we can just identify the unique substrings and check if the pattern holds

public int isMatched(String p, String input) {
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		for (int i = 0; i < p.length(); i++) {
			char ch = p.charAt(i);
			if (map.containsKey(ch)) {
				map.put(ch, map.get(ch) + 1);
			} else {
				map.put(ch, 1);
			}
		}
		HashMap<Character, String> toMatch = new HashMap<Character, String>();
		char first = p.charAt(0);
		int count = map.get(first);
		for (int i = 1; i <= input.length() / count; i++) {
			toMatch.put(first, input.substring(0, i));
			if (startToMatch(p, 1, input, i, toMatch, map, input.length()
					- count * i)) {
				return 1;
			}
			toMatch.clear();
		}
		return 0;
	}

	private boolean startToMatch(String p, int i, String input, int j,
			HashMap<Character, String> toMatch,
			HashMap<Character, Integer> map, int left) {
		if (i == p.length()) {
			return j == input.length();
		}
		char first = p.charAt(i);
		if (toMatch.containsKey(first)) {
			String s = toMatch.get(first);
			int len = s.length();
			if (j + len > input.length()) {
				return false;
			} else {
				if (!s.equalsIgnoreCase(input.substring(j, j + len))) {
					return false;
				} else {
					return startToMatch(p, i + 1, input, j + len, toMatch, map,
							left);
				}
			}
		} else {
			int count = map.get(first);
			for (int k = 1; k <= left / count; k++) {
				toMatch.put(first, input.substring(j, j + k));
				if (startToMatch(p, i + 1, input, j + k, toMatch, map, left
						- count * k)) {
					return true;
				}
				toMatch.remove(first);
			}
			return false;
		}
	}

public static int matching(String target, String pattern) {

int i = 0;
int j = 0;
int patternLength = pattern.length();
for (; i < patternLength; i++) {
for (; j < target.length(); j++) {
if (pattern.charAt(i) == target.charAt(j)) {
break;

}
}
if (j == target.length()) {
break;
}
}
if ((j <= target.length()) && (i == patternLength)) {
return 1;
} else {
return 0;
}
}

My recursive solution. Hopefully the code is self-explanatory, but basically I am using a hashmap to keep track of all the letters I have seen and what values I assume they have.

import java.util.*;

class MatchPattern {
	// assumes both pattern & input are non-null
	static boolean match(String pattern, String input, HashMap<Character, String> seen) {
		int len = pattern.length();
		if(len == 0)
			return input.equals("");
		char ch = pattern.charAt(0);
		boolean seenAlready = seen.containsKey(ch);
		if(len == 1) {
			if(seenAlready)
				return input.equals(seen.get(ch));
			else return true;
		} else if(seenAlready) {
			String existing = seen.get(ch);
			if(input.startsWith(existing) && !input.equals(existing))
				return match(pattern.substring(1), input.substring(existing.length()), seen);
			else return false;
		} else {
			int len2 = input.length();
			for(int i=1; i<len2; i++) {
				String prefix = input.substring(0, i);
				HashSet<String> used = new HashSet<String>(seen.values());
				if(used.contains(prefix))
					continue;
				seen.put(ch, prefix);
				if(match(pattern.substring(1), input.substring(i), seen))
					return true;
				seen.remove(ch);
			}
			return false;
		}
	}

	public static void main(String[] args) {
		HashMap<Character, String> seen = new HashMap<Character, String>();
		System.out.println(match(args[0], args[1], seen) ? "1" : "0");
	}
}

def check(pattern, text, d):
    if len(pattern) == 0 and len(text) == 0:
        return True

    if len(text) == 0 or len(pattern) == 0:
        return False

    if pattern[0] in d:
        tmp = d[pattern[0]]

        if len(tmp) > len(text) or text[:len(tmp)] != tmp:
            return False
        else:
            return check(pattern[1:], text[len(tmp):], d)
    else:
        for i in range(1, len(text)):
            d[pattern[0]] = text[:i]
            if check(pattern[1:], text[i:], d):
                return True
            del d[pattern[0]]

    return False

public boolean containsPattern(final String pattern, final String text){
Set<Character> allChars = new HashSet<Character>();
for (int i=0; i<pattern.length(); i++){
allChars.add(pattern.charAt(i));
}
int patCursor = 0;
boolean first = true;
for (int i=0; i<text.length(); i++){
char ch = text.charAt(i);
if (allChars.contains(ch)){
char patChar = pattern.charAt(patCursor);
if (ch == patChar){
patCursor++;
first = false;
if (patCursor >= pattern.length() ){
patCursor = 0;
}
}else{
if (first){
patCursor = i;
if (patCursor >= pattern.length() ){
patCursor = 0;
}
}else{
return false;
}
}
}
}

return true;
}

Came up with a recursive solution using Hashmaps. Without using regualr expressions, im not sure you can avoid solving this in O(n^x) time.

public boolean findPattern(String pattern, String input, HashMap<Character, String> map, int index){
        if(input.isEmpty()) return false;
        StringBuilder result = new StringBuilder("");
        for(char c : pattern.toCharArray()){
            String piece = map.get(c);
            if(piece == null){
                for(int i = 1+index; i<=input.length(); i++){
                    HashMap <Character, String> copy = new HashMap <Character, String>(map);
                    copy.put(c, input.substring(index, i));
                    if(findPattern(pattern, input, copy, i)) return true;
                }
            }
            else
                result.append(piece);
        }
        //System.out.println(result.toString()+"------"+input.equals(result.toString()));
        return input.equals(result.toString());
    }

Are you sure the input string doesn't have spaces between words? The solution becomes much easier and reasonable with spaces. i.e. "red blue blue red" instead of "redbluebluered". It is an extremely difficult task in attempting to determine where a word begins and ends without some sort of space or delimiter. It is not impossible, but to expect someone to code a solution to that during a short interview is borderline insanity.

This is my implementation in java (works)

public static int find(HashMap<Character,String> map, String word, String pattern){
		if(word.isEmpty() && pattern.isEmpty()){
			return 1;
		}
		if(word.isEmpty() || pattern.isEmpty()){
			return 0;
		}
		char c = pattern.charAt(0);
		String w = map.get(c);
		if (w != null){
			if(!word.startsWith(w))
			{
				return 0;
			}
			return find(map,word.substring(w.length()),pattern.substring(1));
		}
		for(int i = 1 ; i < word.length(); i++){
			String newW = word.substring(0, i);
			map.put(c, newW);
			if (1 == find(map,word.substring(newW.length()),pattern.substring(1))){
				return 1;
			}
			map.remove(c);
		}
		return 0;
	}
	
	public static int find(String word, String pattern){
		return find(new HashMap<Character, String>(),word,pattern);
	}

static void Main(string[] args)
        {
            Console.WriteLine(checkIfFollowsPattern("redbluebluered", "abba").ToString());
            Console.WriteLine(checkIfFollowsPattern("asdasdasdasd", "aaaa").ToString());
            Console.WriteLine(checkIfFollowsPattern("xyzabcxzyabc", "aabb").ToString());
        }

        public static int checkIfFollowsPattern(String input, String pattern)
        {
            Dictionary<char,int> patternHash = new Dictionary<char,int>();
            int i;
            for (i = 0; i < pattern.Length;i++ )
            {
                if (!patternHash.ContainsKey(pattern[i]))
                {
                    patternHash.Add(pattern[i], 1);
                }
                else
                {
                    patternHash[pattern[i]] += 1;
                }       
            }

            string TmpInput = input;

            Dictionary<char, String> patternInputMap = new Dictionary<char, String>();

            for(i = 0; i < patternHash.Count; i++)
            {
                int count = patternHash.ElementAt(i).Value;
                if (TmpInput != null)
                {
                    patternInputMap.Add(patternHash.ElementAt(i).Key, TmpInput[0].ToString());
                    String patternMapString = patternInputMap[patternHash.ElementAt(i).Key];
                    for (int j = 1; j <= TmpInput.Length; j++)
                    {                        
                        if (TmpInput.Substring(j).Contains(patternMapString))
                        {
                            patternMapString = String.Concat(patternMapString, TmpInput[j]);
                        }
                        else
                        {
                            patternMapString = patternMapString.Remove(patternMapString.Length - 1);
                            TmpInput = TmpInput.Replace(patternMapString, "");
                            break;
                        }
                        
                        int patternMapLength =  patternMapString.Length;
                        int k = 0;
                        string testInput = input;
                        while (testInput.Contains(patternMapString))
                        {
                            if (testInput.IndexOf(patternMapString) >= 0)
                            {
                                k++;
                                testInput = testInput.Remove(testInput.IndexOf(patternMapString), patternMapLength);
                            }
                        }
                        if (k == count)
                        {
                            patternInputMap[patternHash.ElementAt(i).Key] = patternMapString;
                        }
                    }
                }
            }

            string checkString = "";
            for (i = 0; i < pattern.Length; i++)
            {
                checkString += patternInputMap[pattern[i]]; 
            }
            if (checkString == input)
            {
                return 1;
            }
            return 0;
        }
    }

There would be potential bugs in this, but I would correct when in some hours after I catch some sleep

static ArrayList<HashMap<Character, Integer>> list = new HashMap<>();

static void combinations (HashMap<Character, Value> map, int N) {
	int total = 0;
	for (Character letter: map.keySet()) {
		total += map.get(letter).frequency * map.get(letter).count;
	}
	if (total == N) {
		list.add(map);
		return;
	}
	else if (total > N) {
		return;
	}

	else {
		for (Character letter: map.keySet()) {
			map.get(letter).count++;
			combinations(map, N);
		}
	}
}

static boolean pattern(ArrayList<HashMap>) {
	boolean result = true;
	for (HashMap<Character, Value> map: list) {
		for (Character letter: map.keySet()) {
			if (map.get(letter).word == null) {
				map.put(letter, word.substring(i, i+map.get(letter).count);
			}
			else if (map.get(letter.word) != word.substring(i, i+ map.get(letter).count)) {
				result = false;
				break;
			}
			if (result) {
				return true;
			}
		}
	}
	return false;
}

public static void main (String[] args) {
	String word = "redbluered";
	String patter = "aba";
	HashMap<Character, Value> map = new HashMap<>();
	for (char c: word.toCharArray()) {
		if (map.get(c) != null) {
			map.put(c, map.get(c).count++);
		}
		else {
			map.put(c, new Value(1, 1, null));
		}
	}
	combinations(map, word.length);
	pattern(list);
}

This question has exponential solution because the assumption of pattern of 2 character does not hold, I am not aware of solution, but I saw this question hint in an interview.

from collections import deque
import copy

P,X = "abba", "redbluebluered" 

def match(P, X):
  node = (P, X, {})
  q = deque()
  q.append(node)
  while q:
    p, x, binding = q.pop()
    #print p, x, binding
    if not p:
      if not x:
        return binding
    elif p[0] in binding:
      bound = binding[p[0]]
      N = len(bound)
      if x[:N] == bound:
        q.append((p[1:], x[N:], binding))
    else:
      for end_ii in range(len(x),0,-1):
        new_binding = copy.copy(binding)
        new_binding[p[0]] = x[:end_ii]
        q.append((p[1:], x[end_ii:], new_binding))
  return None


def match_test(P, X):
  print "Input: ", P, X
  print "Binding: ", match(P, X)

match_test("abba", "redbluebluered")
match_test("aaaa", "asdasdasdasd")
match_test("aabb", "xyzabcxzyabc")

It's not efficient one but it will solve the problem .

Let number of distinct characters in pattern is fixed or at most (k).
But it will take lot of time to just find solution of Xi where i is from 1 to k. If it finds such Xi then it will
check for correctness.If there is more than one solution exists then we have to check for all.
Run k nested for loop to find  Xi if sum of all Xi is equal to string length then 
find 
a_1 = str_1
a_2 = str_2 
... 
a_k = str_k

Now concatenate  str_i using  a_i and pattern and check if it's equal to given string or not .
If yes then print yes otherwise not 

How to find a_m ?
To find a_m we can take help of pattern and  initial few characters from input string and pattern character as  a_j then 
find another a_p using a_j , pattern and given input string . 

Let's give an example.
pattern = "abba" and input string is "redbluebluered"
x1+x2 = 7 
so we have 
x1 = 0 and x2 =7 : a="" and b="redblue" 
x1 = 1 and x2 =6   : a="r" and b = "edblue"
x1 = 2 and x2 = 5  : a="re" and b="dblue"
x1 = 3 and x2 = 4  :a="red" and b="blue"
x1 = 4 and x2 = 3   :a="redb" and b ="lue"
x1 = 5 and x2 = 2   :a="redbl" and b="ue"
x1 = 6  and x2= 1  : a="redblu" and  b="e" 
x1 = 7 and x2 = 0   :a="redblue" and b="" 
We can see that only string a = "red" and b= "blue" satisfied the pattern and string "redbluebluered" .

Yep, it's a dfs problem.
Use two maps, one map to record the match between each char in pattern and each string segment in target string s; one map to record the inverse. C++

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

class Solution{
public:
	bool JudgePattern(string pattern, string s){
		if(pattern.empty()) return s.empty();
		if(s.empty()) return emptyOrSingleLetter(pattern);
		unordered_map<char, string> psmap;
		unordered_map<string, char> spmap;
		return judgeCore(pattern, 0, s, 0, psmap, spmap);
	}
private:
	bool judgeCore(string pattern, int t, string s, int p, unordered_map<char, string> &psmap, unordered_map<string, char> &spmap){
		int plen = pattern.length(); int slen = s.length();
		if(t == plen && p == slen) return true;
		if(t == plen || p == slen) return false;
		if(psmap.find(pattern[t]) != psmap.end()){
			if(p+psmap[pattern[t]].length() > slen) return false;
			string tmpstr = s.substr(p, psmap[pattern[t]].length());
			if(tmpstr == psmap[pattern[t]])
				return judgeCore(pattern, t+1, s, p+psmap[pattern[t]].length(), psmap, spmap);
		}else{
			for(int q = p+1; q <= slen; ++q){
				string subs = s.substr(p, q-p);
				if(spmap.find(subs) == spmap.end()){
					spmap[subs] = pattern[t];
					psmap[pattern[t]] = subs;
					if(judgeCore(pattern, t+1, s, q, psmap, spmap))
						return true;
					psmap.erase(psmap.find(pattern[t]));
					spmap.erase(spmap.find(subs));
				}
			}
		}
		return false;
	}

	bool emptyOrSingleLetter(string pattern){
		if(pattern.empty()) return true;
		for(int i = 1; i < pattern.length(); ++i){
			if(pattern[i] != pattern[0]) return false;
		}
		return true;
	}
};


int main(){
	Solution sln;
	cout << sln.JudgePattern("aaa", "") << endl;
	cout << sln.JudgePattern("aba", "red") << endl;
	cout << sln.JudgePattern("aabb", "xyzxyzabab") << endl;
	cout << sln.JudgePattern("aabb", "xyzxyzab") << endl;
	cout << sln.JudgePattern("fbcf", "xyzdoxyz") << endl;

	return 0;
}

What about using a trie ??

the method can't be named DFS, it can be named as backtracking.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

#define OFFSET 97
vector<int> exists;//array of existing int vals of char


int A[1000000], Q[1000000];
int letters[26];//keeps track of the NUMBER instances where this shows up in the initial pattern

string words[26];//stores the substring we are to test

string p = "abba";
int psize = 4;
//
string tryCombo(){
    string str = "";
    for(int i = 0; i < psize; i++){
        //cout << "in tryCombo(): OFFSET::(int)p.at(i)" << OFFSET << "::"<< (int)p.at(i) << endl;
        str += words[  (int)p.at(i)- OFFSET];
        cout << words[  (int)p.at(i)- OFFSET] << " ";
    }
    cout << endl;
    return str;
}

//EVERY TIME THIS IS CALLED, ITS EITHER:
// 1. SETTING A PATTERN KEY TO A WORD, OR 
// 2. SETTING A PATTERN KEY TO A WORD AND ATTEMPTING A CHECK IF IT IS THE LAST KEY
bool permute(string s, int blen, int offset, int charintval){
    //offset is how much of the string has been used already for another key
    //char int val is the number ordering in exists                                     
    if( exists[charintval] == exists.back()){
        //if we ever reach here, call trycombo since it
        //is the last pattern symbol to be matched
        for(int i = 0; i < blen; i++){
            words[charintval] = s.substr(offset+i, (s.length()/letters[exists[charintval]]) - (offset+i ));
            if(tryCombo() == s){
                return true;
            }
        }
        return false;
    }else{
        for(int i = 0; i < blen; i++){
            words[charintval] = s.substr(offset+i);
            if(permute(s,blen-i,offset+i, charintval+1)){
                return true;
            }
        }
        return false;
    }
}

int main() {
    string a = "abba"; // used as p in tryCombo()
    string b = "redbluebluered";
    int alen = a.length();//4, used as psize in tryCombo()
    int blen = b.length();//14 in this case
    
    int distinct = 0;//number of distinct vals... should be
                    //essential since this determines the permutation...
    
    for(int i = 0;i<26;i++)
        words[i] = "";
                    
    //ASSUMTIONS:
    // Only 1 pattern value can be empty string
    for(int i = 0; i < alen; i++){
        if( letters[ ((int)a.at(i))-OFFSET ] == 0 ){
            distinct++;//increment number of existing vals
            exists.push_back(((int)a.at(i))-OFFSET );// add the index of the corresponding 
                                                // character casted as int
        }
        letters[ ((int)a.at(i))-OFFSET ]++;
    }
    
    //cout << "letters at i"<<endl;
    //for(int i = 0; i < 26; i++){
    //    cout << letters[i] << " " << i << endl;
    //}
    
    if(distinct == 1){
        cout << a << " and " << b << " matches!" << endl;
    }else{
        //need something to get all posssible combinations of string lengths to try that add 
        //up to blen.....
        //blen needs to be a bit dynamic since if there are only 2 distinct, then 1 can be empty
        // if d = 2, the break flag that is < for the first encountered letter needs to be
        // 
        
        int blenflag = blen;
        if(distinct > 2)
            blenflag -= (distinct-2);
        
        for(int i = 0; i < blenflag/letters[0]+1; i++){
            words[0] = b.substr(0,i);
            cout << "initial permute w/ params " << b << " " << blenflag-(i*letters[0]) << " 1 " << i << endl;
            if(permute(b,blenflag-(i*letters[0]),i,1)){
                cout << "GG" << endl;
                break;
            }
        }
    }
   return 0;
}

public class StringPatternMatch {

    static boolean isMatch(String str, int iStr, String pattern, int iPat, Map<Character, String> map){
        if(str==null || pattern == null){
            return false;
        }
        if(str.length() == iStr && pattern.length()==iPat){
            return true;
        }
        if((str.length()==iStr && pattern.length() != iPat) ||
                (str.length() != iStr && pattern.length()==iPat)){
            return false;
        }
        if(map.containsKey(pattern.toCharArray()[iPat])){
            String val = map.get(pattern.toCharArray()[iPat]);
            if(iStr+val.length() <= str.length() && val.equals(str.substring(iStr, iStr+val.length()))){
                return isMatch(str, iStr+val.length(), pattern, iPat+1, map);
            }
            return false;
        }

        for (int i = iStr; i < str.length(); i++) {
            map.put(pattern.toCharArray()[iPat], str.substring(iStr, i+1));
            if (!isMatch(str, i + 1, pattern, iPat + 1, map)) {
                map.remove(pattern.toCharArray()[iPat]);
            } else {
                return true;
            }
        }

        return false;
    }

    static boolean isMatch(String str, String pattern){
        Map<Character, String> map = new HashMap<Character, String>();
        boolean isM = isMatch(str, 0, pattern, 0, map);
        System.out.println(map);
        return isM;
    }

    public static void main(String args[]){
        String str = "redbluebluered";
        String pattern = "abba";

        System.out.println("str: "+str+ ", pattern: "+pattern+ ", isMatch: "+isMatch(str, pattern));
    }

}

Solving this efficiently is a dynamic programming problem.

This question requires some knowledge about the input alphabet. Who's to say xyzabc isn't just one iteration of the pattern?

This question requires some knowledge about the input alphabet. Who's to say xyzabc isn't just one iteration of the pattern?

This question requires some knowledge about the input alphabet. Who's to say xyzabc isn't just one iteration of the pattern?

This question requires some knowledge about the input alphabet. Who's to say xyzabc isn't just one iteration of the pattern?

This question requires some knowledge about the input alphabet. Who's to say xyzabc isn't just one iteration of the pattern?

This question requires some knowledge about the input alphabet. Who's to say xyzabc isn't just one iteration of the pattern?

This question requires some knowledge about the input alphabet. Who's to say xyzabc isn't just one iteration of the pattern?