Dropbox Interview Question: Question was Given a pattern... | Glassdoor

Dropbox Interview Question: Question was Given a pattern... | Glassdoor

Question was “Given a pattern and a string input – find if the string follows the same pattern and return 0 or 1.
Examples:
1) Pattern : “abba”, input: “redbluebluered” should return 1.
2) Pattern: “aaaa”, input: “asdasdasdasd” should return 1.
3) Pattern: “aabb”, input: “xyzabcxzyabc” should return 0.
complexity analysis:
Suppose the input size is n.
For each different character in pattern, it needs to try different length, so it increase the complexity by n times.
if there are k different characters in the pattern, the complexity will be O(n, k+1)

bool isSamePatternHelper(string& pattern, int pIndex, string& input, int iIndex, unordered_map<char, string>& hash) {

    if (pIndex == pattern.size() && iIndex == input.size()) {

        return true;

    }

    if (pIndex == pattern.size() || iIndex == input.size()) {

        return false;

    }

    char c = pattern[pIndex];

    if (hash.find(c) != hash.end()) {

        string toMatch = hash[c];

        for (int i = 0; i < toMatch.size(); i++) {

            if (iIndex >= input.size() || input[iIndex] != toMatch[i]) {

                return false;

            }

            iIndex++;

        }

        return isSamePatternHelper(pattern, pIndex + 1, input, iIndex, hash);

    } else {

        // try all possible

        bool flag = false;

        for (int i = iIndex; i < input.size(); i++) {

            string toMatch = input.substr(iIndex, i - iIndex + 1);

            hash[c] = toMatch;

            flag |= isSamePatternHelper(pattern, pIndex + 1, input, i + 1, hash);

            hash.erase(c);

            if (flag) {

                return true;

            }

        }

        return false;

    }

}

 

bool isSamePattern(string& pattern, string& input) {

    int patternSize = pattern.size();

    int inputSize = input.size();

    if (inputSize < patternSize)

        return false;

    unordered_map<char, string> hash;

    return isSamePatternHelper(pattern, 0, input, 0, hash);

}

 

int main(){

    string pattern = "abab";

    string input = "redblueredblue";

    bool ret = isSamePattern(pattern, input);

    cout << ret << endl;

    return 0;

http://www.mitbbs.com/article_t/JobHunting/32817129.html
让start1为string里的起始点，start2为pattern里的起始点，初始值都为0.

        boolean dfs(String str, int start1, char[] pattern, int start2, Map<
Character, String> map, Set<String> visited) {
        if (start1 == str.length() || start2 == pattern.length) {
            return start1 == str.length() && start2 == pattern.length;
        }

                char ch = pattern[start2++];
                if (map.containsKey(ch)) {
                   在map里找到对应单词
                   if(str能够从start1开始取到这个单词）
                                return dfs(str, start1 + 下个单词长度, 
pattern, start2, map, visited);
                } else {
                   for (int end = start1 + 1; end <= str.length(); ++end) {
                               让nextWord为start1和end之间的substring,
                                if(nextWord在visited中) continue;
                map.put(ch, nextWord);
                visited.add(nextWord);
                if (haveWordPattern(str, end, pattern, start2, map, visited)
) {
                    return true;
                }
                map.remove(ch);
                visited.remove(nextWord);
                   }

                   return false;
        }

其实里面还可以加点剪枝代码，不过大概就是这样了。


Read full article from Dropbox Interview Question: Question was Given a pattern... | Glassdoor