我的朋友刚刚在 Google 面试时被拒绝了，因为他不能给出这个问题的解决方案。
我自己也要在几天后面试，但似乎无法想出解决方法。
以下是问题：
给定一个模式，例如 [a b a b]。还给定一个字符串，例如 "redblueredblue"。我需要编写一个程序来告诉我字符串是否遵循给定的模式。
一些例子：
模式：[a b b a] 字符串：catdogdogcat 返回 1
模式：[a b a b] 字符串：redblueredblue 返回 1
模式：[a b b a] 字符串：redblueredblue 返回 0
我想到了一些方法，比如获取模式中唯一字符的数量，然后找到那么多个唯一的子字符串，再使用哈希映射表将其与模式进行比较。但是，如果 a 的子字符串是 b 的一部分，这种方法就有问题了。
如果你们中任何人能帮助我解决这个问题，那就太好了。:)
更新：
添加信息：模式中可以有任意数量的字符（a-z）。两个字符不会代表相同的子字符串。并且，一个字符不能表示空字符串。
a 或 b 的长度，但两个 a 长度相同，两个b长度也相同。 因此，给定字符串的划分方式并不是很多。
例如：
模式 = [a b a b] ，给定字符串 = redblueredblue（总共14个字符）
|a|（a的长度）= 1，则为 a 分配2个字符，剩下12个字符供 b 使用，即|b|= 6。 划分后的字符串= r edblue r edblue。哇，这立刻就匹配了！|a| = 2, |b| = 5 -> 划分后的字符串= re dblue re dblue -> 匹配示例2：
模式 = [a b a b] ，给定字符串 = redbluebluered（总共14个字符）
|a| = 1, |b| = 6 -> 划分后的字符串= r edblue b luered -> 不匹配|a| = 2, |b| = 5 -> 划分后的字符串= re dblue bl uered -> 不匹配|a| = 3, |b| = 4 -> 划分后的字符串= red blue blu ered -> 不匹配剩下的部分无需检查，因为如果您将 a 和 b 互换位置，则情况是相同的。
[a b c a b c] 的模式是什么？
[a a b b]或[b b a a]这样的模式，它会起作用吗？ - user7098526你只需要使用回溯引用把这个模式转换成正则表达式，例如（在已加载“re”模块的 Python 3 中）：
>>> print(re.match('(.+)(.+)\\2\\1', 'catdogdogcat'))
<_sre.SRE_Match object; span=(0, 12), match='catdogdogcat'>
>>> print(re.match('(.+)(.+)\\1\\2', 'redblueredblue'))
<_sre.SRE_Match object; span=(0, 14), match='redblueredblue'>
>>> print(re.match('(.+)(.+)\\2\\1', 'redblueredblue'))
None
正则表达式看起来相当简单易懂。如果您需要支持多于9个反向引用，您可以使用命名组 - 请参阅Python正则表达式文档。
这里是一个Java回溯解决方案。源链接。
public class Solution {
public boolean isMatch(String str, String pat) {
Map<Character, String> map = new HashMap<>();
return isMatch(str, 0, pat, 0, map);
}
boolean isMatch(String str, int i, String pat, int j, Map<Character, String> map) {
// base case
if (i == str.length() && j == pat.length()) return true;
if (i == str.length() || j == pat.length()) return false;
// get current pattern character
char c = pat.charAt(j);
// if the pattern character exists
if (map.containsKey(c)) {
String s = map.get(c);
// then check if we can use it to match str[i...i+s.length()]
if (i + s.length() > str.length() || !str.substring(i, i + s.length()).equals(s)) {
return false;
}
// if it can match, great, continue to match the rest
return isMatch(str, i + s.length(), pat, j + 1, map);
}
// pattern character does not exist in the map
for (int k = i; k < str.length(); k++) {
// create or update the map
map.put(c, str.substring(i, k + 1));
// continue to match the rest
if (isMatch(str, k + 1, pat, j + 1, map)) {
return true;
}
}
// we've tried our best but still no luck
map.remove(c);
return false;
}
}
我使用正则表达式解决了这个语言生成问题。
def wordpattern( pattern, string):
'''
input: pattern 'abba'
string 'redbluebluered'
output: 1 for match, 2 for no match
'''
# assemble regex into something like this for 'abba':
# '^(?P<A>.+)(?P<B>.+)(?P=B)(?P=A)$'
p = pattern
for c in pattern:
C = c.upper()
p = p.replace(c,"(?P<{0}>.+)".format(C),1)
p = p.replace(c,"(?P={0})".format(C),len(pattern))
p = '^' + p + '$'
# check for a preliminary match
if re.search(p,string):
rem = re.match(p,string)
seen = {}
# check to ensure that no points in the pattern share the same match
for c in pattern:
s = rem.group(c.upper())
# has match been seen? yes, fail, no continue
if s in seen and seen[s] != c:
return 0
seen[s] = c
# success
return 1
# did not hit the search, fail
return 0
import java.io.IOException;
import java.util.*;
public class Test {
public static void main(String[] args) throws IOException {
int res;
res = wordpattern("abba", "redbluebluered");
System.out.println("RESULT: " + res);
}
static int wordpattern(String pattern, String input) {
int patternSize = 1;
boolean res = findPattern(pattern, input, new HashMap<Character, String>(), patternSize);
while (!res && patternSize < input.length())
{
patternSize++;
res = findPattern(pattern, input, new HashMap<Character, String>(), patternSize);
}
return res ? 1 : 0;
}
private static boolean findPattern(String pattern, String input, Map<Character, String> charToValue, int patternSize) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < pattern.length(); i++) {
char c = pattern.charAt(i);
if (charToValue.containsKey(c)) {
sb.append(charToValue.get(c));
} else {
// new character in pattern
if (sb.length() + patternSize > input.length()) {
return false;
} else {
String substring = input.substring(sb.length(), sb.length() + patternSize);
charToValue.put(c, substring);
int newPatternSize = 1;
boolean res = findPattern(pattern, input, new HashMap<>(charToValue), newPatternSize);
while (!res && newPatternSize + sb.length() + substring.length() < input.length() - 1) {
newPatternSize++;
res = findPattern(pattern, input, new HashMap<>(charToValue), newPatternSize);
}
return res;
}
}
}
return sb.toString().equals(input) && allValuesUniq(charToValue.values());
}
private static boolean allValuesUniq(Collection<String> values) {
Set<String> set = new HashSet<>();
for (String v : values) {
if (!set.add(v)) {
return false;
}
}
return true;
}
}
我在 C# 上实现了这个功能。尝试寻找一个干净的解决方案，但没有找到。所以我会将它添加到这里。
private static bool CheckIfStringFollowOrder(string text, string subString)
{
int subStringLength = subString.Length;
if (text.Length < subStringLength) return false;
char x, y;
int indexX, indexY;
for (int i=0; i < subStringLength -1; i++)
{
indexX = -1;
indexY = -1;
x = subString[i];
y = subString[i + 1];
indexX = text.LastIndexOf(x);
indexY = text.IndexOf(y);
if (y < x || indexX == -1 || indexY == -1)
return false;
}
return true;
}
class StringPattern{
public:
int n, pn;
string str;
unordered_map<string, pair<string, int>> um;
vector<string> p;
bool match(string pat, string str_) {
p.clear();
istringstream istr(pat);
string x;
while(istr>>x) p.push_back(x);
pn=p.size();
str=str_;
n=str.size();
um.clear();
return dfs(0, 0);
}
bool dfs(int i, int c) {
if(i>=n) {
if(c>=pn){
return 1;
}
}
if(c>=pn) return 0;
for(int len=1; i+len-1<n; len++) {
string sub=str.substr(i, len);
if(um.count(p[c]) && um[p[c]].fi!=sub
|| um.count(sub) && um[sub].fi!=p[c]
)
continue;
//cout<<"str:"<<endl;
//cout<<p[c]<<" "<<sub<<endl;
um[p[c]].fi=sub;
um[p[c]].se++;
um[sub].fi=p[c];
um[sub].se++;
//um[sub]=p[c];
if(dfs(i+len, c+1)) return 1;
um[p[c]].se--;
if(!um[p[c]].se) um.erase(p[c]);
um[sub].se--;
if(!um[sub].se) um.erase(sub);
//um.erase(sub);
}
return 0;
}
};
我的解决方案需要两个侧面的哈希映射，并且还需要计算哈希映射的数量
function isMatch(pattern, str){
var map = {}; //store the pairs of pattern and strings
function checkMatch(pattern, str) {
if (pattern.length == 0 && str.length == 0){
return true;
}
//if the pattern or the string is empty
if (pattern.length == 0 || str.length == 0){
return false;
}
//store the next pattern
var currentPattern = pattern.charAt(0);
if (currentPattern in map){
//the pattern has alredy seen, check if there is a match with the string
if (str.length >= map[currentPattern].length && str.startsWith(map[currentPattern])){
//there is a match, try all other posibilities
return checkMatch(pattern.substring(1), str.substring(map[currentPattern].length));
} else {
//no match, return false
return false;
}
}
//the current pattern is new, try all the posibilities of current string
for (var i=1; i <= str.length; i++){
var stringToCheck = str.substring(0, i);
//store in the map
map[currentPattern] = stringToCheck;
//try the rest
var match = checkMatch(pattern.substring(1), str.substring(i));
if (match){
//there is a match
return true;
} else {
//if there is no match, delete the pair from the map
delete map[currentPattern];
}
}
return false;
}
return checkMatch(pattern, str);
}
Python解决方案基于Java解决方案，链接如下：https://www.algo.monster/problems/word_pattern_ii
def helper(pattern, s, idxPattern, idxString, myMap, mySet):
if (idxPattern == len(pattern)) and (idxString == len(s)):
return True
if (idxPattern >= len(pattern)) or (idxString >= len(s)):
return False
thisChar = pattern[idxPattern]
#print ("At Char: ", thisChar, " at location: ", idxPattern)
for idxK in range(idxString + 1, len(s) + 1):
subString = s[idxString:idxK]
if (thisChar not in myMap) and (subString not in mySet) :
myMap[thisChar] = subString
mySet.add(subString)
# print ("Before Map {0}, Set: {1}".format(myMap, mySet))
if helper(pattern, s, idxPattern + 1, idxK, myMap, mySet):
return True
myMap.pop(thisChar)
mySet.remove(subString)
# print ("After Map {0}, Set: {1}".format(myMap, mySet))
elif (thisChar in myMap) and (myMap[thisChar] == subString):
if helper(pattern, s, idxPattern + 1, idxK, myMap, mySet):
return True
def word_pattern_match(pattern: str, s: str) -> bool:
# WRITE YOUR BRILLIANT CODE HERE
print ("Pattern {0}, String {1}".format(pattern, s))
if (len(pattern) == 0) and (len(s) == 0):
return True
if (len(pattern) == 0):
return False
myMap = dict()
mySet = set()
return helper(pattern, s, 0, 0, myMap, mySet)
if __name__ == '__main__':
pattern = input()
s = input()
res = word_pattern_match(pattern, s)
print('true' if res else 'false')
我想不出比暴力解决方案更好的了：尝试单词的每种可能的分割（这本质上就是Jan所描述的）。
运行时间复杂度为O(n^(2m))，其中m是模式的长度，n是字符串的长度。
以下是代码示例（我让我的代码返回实际映射而不仅仅是0或1。将代码修改为返回0或1很容易）：
import java.util.Arrays;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class StringBijection {
public static void main(String[] args) {
String chars = "abaac";
String string = "johnjohnnyjohnjohncodes";
List<String> stringBijection = getStringBijection(chars, string);
System.out.println(Arrays.toString(stringBijection.toArray()));
}
public static List<String> getStringBijection(String chars, String string) {
if (chars == null || string == null) {
return null;
}
Map<Character, String> bijection = new HashMap<Character, String>();
Deque<String> assignments = new ArrayDeque<String>();
List<String> results = new ArrayList<String>();
boolean hasBijection = getStringBijection(chars, string, 0, 0, bijection, assignments);
if (!hasBijection) {
return null;
}
for (String result : assignments) {
results.add(result);
}
return results;
}
private static boolean getStringBijection(String chars, String string, int charIndex, int stringIndex, Map<Character, String> bijection, Deque<String> assignments) {
int charsLen = chars.length();
int stringLen = string.length();
if (charIndex == charsLen && stringIndex == stringLen) {
return true;
} else if (charIndex == charsLen || stringIndex == stringLen) {
return false;
}
char currentChar = chars.charAt(charIndex);
List<String> possibleWords = new ArrayList<String>();
boolean charAlreadyAssigned = bijection.containsKey(currentChar);
if (charAlreadyAssigned) {
String word = bijection.get(currentChar);
possibleWords.add(word);
} else {
StringBuilder word = new StringBuilder();
for (int i = stringIndex; i < stringLen; ++i) {
word.append(string.charAt(i));
possibleWords.add(word.toString());
}
}
for (String word : possibleWords) {
int wordLen = word.length();
int endIndex = stringIndex + wordLen;
if (endIndex <= stringLen && string.substring(stringIndex, endIndex).equals(word)) {
if (!charAlreadyAssigned) {
bijection.put(currentChar, word);
}
assignments.addLast(word);
boolean done = getStringBijection(chars, string, charIndex + 1, stringIndex + wordLen, bijection, assignments);
if (done) {
return true;
}
assignments.removeLast();
if (!charAlreadyAssigned) {
bijection.remove(currentChar);
}
}
}
return false;
}
}