模式匹配面试Q.

Question

我最近在接受采访时问他以下问题:

编写一个函数,如果字符串与模式匹配则返回true,否则返回false

模式:每个项目1个字符,(az),输入:空格分隔的字符串

这是我解决第一个问题的方法:

static boolean isMatch(String pattern, String input) {
    char[] letters = pattern.toCharArray();
    String[] split = input.split("\\s+");

    if (letters.length != split.length) {
        // early return - not possible to match if lengths aren't equal
        return false;
    }

    Map<String, Character> map = new HashMap<>();
    // aaaa test test test1 test1
    boolean used[] = new boolean[26];
    for (int i = 0; i < letters.length; i++) {
        Character existing = map.get(split[i]);
        if (existing == null) {
            // put into map if not found yet
            if (used[(int)(letters[i] - 'a')]) {
                return false;
            }

            used[(int)(letters[i] - 'a')] = true;
            map.put(split[i], letters[i]);
        } else {
            // doesn't match - return false
            if (existing != letters[i]) {
                return false;
            }
        }
    }

    return true;
}

public static void main(String[] argv) {
    System.out.println(isMatch("aba", "blue green blue"));
    System.out.println(isMatch("aba", "blue green green"));
}

问题的下一部分让我难过:

如果输入中没有分隔符,请编写相同的函数.

例如:

isMatch("aba", "bluegreenblue") -> true
isMatch("abc","bluegreenyellow") -> true
isMatch("aba", "t1t2t1") -> true
isMatch("aba", "t1t1t1") -> false
isMatch("aba", "t1t11t1") -> true
isMatch("abab", "t1t2t1t2") -> true
isMatch("abcdefg", "ieqfkvu") -> true
isMatch("abcdefg", "bluegreenredyellowpurplesilvergold") -> true
isMatch("ababac", "bluegreenbluegreenbluewhite") -> true
isMatch("abdefghijklmnopqrstuvwxyz", "zyxwvutsrqponmlkjihgfedcba") -> true

我编写了一个强力解决方案(生成所有可能的大小输入字符串的分割letters.length并依次检查isMatch),但是访调员说这不是最优的.

我不知道如何解决这部分问题,这甚至可能还是我遗漏了什么？

他们正在寻找具有时间复杂度的东西O(M x N ^ C),其中M是模式的长度,N是输入的长度,C是一些常数.

澄清

• 我不是在寻找正则表达式解决方案,即使它有效.
• 我不是在寻找能够产生所有可能的分裂并检查它们的天真解决方案,即使是优化也是如此,因为这将始终是指数时间.

Answer 1

可以优化回溯解决方案.我们可以"在飞行中"检查它,而不是先生成所有拆分,然后检查它是否是有效的.假设我们已经分割了p初始字符串的前缀(带有长度)并且已经匹配i了模式中的字符.我们来看看这个i + 1角色吧.

1. 如果前缀中有一个字符串对应于i + 1字母,我们应该检查从该位置开始的子字符串p + 1是否等于它.如果是,我们只是继续i + 1和p + the length of this string.否则,我们可以杀死这个分支.

2. 如果没有这样的字符串,我们应该尝试从该位置开始p + 1并在其后的某个位置结束的所有子串.

我们还可以使用以下想法来减少解决方案中的分支数量:我们可以估计尚未处理的模式后缀的长度(我们知道已经代表某些字符串的字母的长度,以及我们知道模式中任何字母的字符串长度的一个微不足道的下限(它是1)).如果初始字符串的剩余部分太短而无法与模式的其余部分匹配,它允许我们终止分支.

此解决方案仍具有指数时间复杂度,但它可以比生成所有拆分更快地工作,因为无效解决方案可以更早地丢弃,因此可达状态的数量可以显着减少.

Answer 2

更新：这是我的解决方案。基于我之前所做的解释。

import com.google.common.collect.*;
import org.apache.commons.lang3.StringUtils;
import org.apache.commons.lang3.tuple.Pair;
import org.apache.commons.math3.util.Combinations;

import java.util.*;

/**
 * Created by carlos on 2/14/15.
 */
public class PatternMatcher {

    public static boolean isMatch(char[] pattern, String searchString){
        return isMatch(pattern, searchString, new TreeMap<Integer, Pair<Integer, Integer>>(), Sets.newHashSet());
    }
    private static boolean isMatch(char[] pattern, String searchString, Map<Integer, Pair<Integer, Integer>> candidateSolution, Set<String> mappedStrings) {
        List<Integer> occurrencesOfCharacterInPattern = getNextUnmappedPatternOccurrences(candidateSolution, pattern);
        if(occurrencesOfCharacterInPattern.size() == 0)
            return isValidSolution(candidateSolution, searchString, pattern, mappedStrings);
        List<Pair<Integer, Integer>> sectionsOfUnmappedStrings = sectionsOfUnmappedStrings(searchString, candidateSolution);
        if(sectionsOfUnmappedStrings.size() == 0)
            return false;
        String firstUnmappedString = substring(searchString, sectionsOfUnmappedStrings.get(0));


        for (int substringSize = 1; substringSize <= firstUnmappedString.length(); substringSize++) {
            String candidateSubstring = firstUnmappedString.substring(0, substringSize);
            if(mappedStrings.contains(candidateSubstring))
                continue;
            List<Pair<Integer, Integer>> listOfAllOccurrencesOfSubstringInString = Lists.newArrayList();
            for (int currentIndex = 0; currentIndex < sectionsOfUnmappedStrings.size(); currentIndex++) {
                Pair<Integer,Integer> currentUnmappedSection = sectionsOfUnmappedStrings.get(currentIndex);
                List<Pair<Integer, Integer>> occurrencesOfSubstringInString =
                        findAllInstancesOfSubstringInString(searchString, candidateSubstring,
                                currentUnmappedSection);
                for(Pair<Integer,Integer> possibleAddition:occurrencesOfSubstringInString) {
                    listOfAllOccurrencesOfSubstringInString.add(possibleAddition);
                }
            }

            if(listOfAllOccurrencesOfSubstringInString.size() < occurrencesOfCharacterInPattern.size())
                return false;

            Iterator<int []> possibleSolutionIterator =
                    new Combinations(listOfAllOccurrencesOfSubstringInString.size(),
                            occurrencesOfCharacterInPattern.size()).iterator();
            iteratorLoop:
            while(possibleSolutionIterator.hasNext()) {
                Set<String> newMappedSets = Sets.newHashSet(mappedStrings);
                newMappedSets.add(candidateSubstring);
                TreeMap<Integer,Pair<Integer,Integer>> newCandidateSolution = Maps.newTreeMap();
                // why doesn't Maps.newTreeMap(candidateSolution) work?
                newCandidateSolution.putAll(candidateSolution);

                int [] possibleSolutionIndexSet = possibleSolutionIterator.next();

                for(int i = 0; i < possibleSolutionIndexSet.length; i++) {
                    Pair<Integer, Integer> candidatePair = listOfAllOccurrencesOfSubstringInString.get(possibleSolutionIndexSet[i]);
                    //if(candidateSolution.containsValue(Pair.of(0,1)) && candidateSolution.containsValue(Pair.of(9,10)) && candidateSolution.containsValue(Pair.of(18,19)) && listOfAllOccurrencesOfSubstringInString.size() == 3 && candidateSolution.size() == 3 && possibleSolutionIndexSet[0]==0 && possibleSolutionIndexSet[1] == 2){
                    if (makesSenseToInsert(newCandidateSolution, occurrencesOfCharacterInPattern.get(i), candidatePair))
                        newCandidateSolution.put(occurrencesOfCharacterInPattern.get(i), candidatePair);
                    else
                        break iteratorLoop;
                }

                if (isMatch(pattern, searchString, newCandidateSolution,newMappedSets))
                    return true;
            }

        }
        return false;
    }

    private static boolean makesSenseToInsert(TreeMap<Integer, Pair<Integer, Integer>> newCandidateSolution, Integer startIndex, Pair<Integer, Integer> candidatePair) {
        if(newCandidateSolution.size() == 0)
            return true;

        if(newCandidateSolution.floorEntry(startIndex).getValue().getRight() > candidatePair.getLeft())
            return false;

        Map.Entry<Integer, Pair<Integer, Integer>> ceilingEntry = newCandidateSolution.ceilingEntry(startIndex);
        if(ceilingEntry !=null)
            if(ceilingEntry.getValue().getLeft() < candidatePair.getRight())
                return false;

        return true;
    }

    private static boolean isValidSolution( Map<Integer, Pair<Integer, Integer>> candidateSolution,String searchString, char [] pattern, Set<String> mappedStrings){
        List<Pair<Integer,Integer>> values = Lists.newArrayList(candidateSolution.values());
        return  areIntegersConsecutive(Lists.newArrayList(candidateSolution.keySet())) &&
                arePairsConsecutive(values) &&
                values.get(values.size() - 1).getRight() == searchString.length() &&
                patternsAreUnique(pattern,mappedStrings);
    }

    private static boolean patternsAreUnique(char[] pattern, Set<String> mappedStrings) {
        Set<Character> uniquePatterns = Sets.newHashSet();
        for(Character character:pattern)
            uniquePatterns.add(character);

        return uniquePatterns.size() == mappedStrings.size();
    }

    private static List<Integer> getNextUnmappedPatternOccurrences(Map<Integer, Pair<Integer, Integer>> candidateSolution, char[] searchArray){
        List<Integer> allMappedIndexes = Lists.newLinkedList(candidateSolution.keySet());
        if(allMappedIndexes.size() == 0){
            return occurrencesOfCharacterInArray(searchArray,searchArray[0]);
        }
        if(allMappedIndexes.size() == searchArray.length){
            return Lists.newArrayList();
        }
        for(int i = 0; i < allMappedIndexes.size()-1; i++){
            if(!areIntegersConsecutive(allMappedIndexes.get(i),allMappedIndexes.get(i+1))){
                return occurrencesOfCharacterInArray(searchArray,searchArray[i+1]);
            }
        }
        List<Integer> listOfNextUnmappedPattern = Lists.newArrayList();
        listOfNextUnmappedPattern.add(allMappedIndexes.size());
        return listOfNextUnmappedPattern;
    }

    private static String substring(String string, Pair<Integer,Integer> bounds){
        try{
            string.substring(bounds.getLeft(),bounds.getRight());
        }catch (StringIndexOutOfBoundsException e){
            System.out.println();
        }
        return string.substring(bounds.getLeft(),bounds.getRight());
    }

    private static List<Pair<Integer, Integer>> sectionsOfUnmappedStrings(String searchString, Map<Integer, Pair<Integer, Integer>> candidateSolution) {
        if(candidateSolution.size() == 0) {
            return Lists.newArrayList(Pair.of(0, searchString.length()));
        }
        List<Pair<Integer, Integer>> sectionsOfUnmappedStrings = Lists.newArrayList();
        List<Pair<Integer,Integer>> allMappedPairs = Lists.newLinkedList(candidateSolution.values());

        // Dont have to worry about the first index being mapped because of the way the first candidate solution is made
        for(int i = 0; i < allMappedPairs.size() - 1; i++){
            if(!arePairsConsecutive(allMappedPairs.get(i), allMappedPairs.get(i + 1))){
                Pair<Integer,Integer> candidatePair = Pair.of(allMappedPairs.get(i).getRight(), allMappedPairs.get(i + 1).getLeft());
                sectionsOfUnmappedStrings.add(candidatePair);
            }
        }

        Pair<Integer,Integer> lastMappedPair = allMappedPairs.get(allMappedPairs.size() - 1);
        if(lastMappedPair.getRight() != searchString.length()){
            sectionsOfUnmappedStrings.add(Pair.of(lastMappedPair.getRight(),searchString.length()));
        }

        return sectionsOfUnmappedStrings;
    }

    public static boolean areIntegersConsecutive(List<Integer> integers){
        for(int i = 0; i < integers.size() - 1; i++)
            if(!areIntegersConsecutive(integers.get(i),integers.get(i+1)))
                return false;
        return true;
    }

    public static boolean areIntegersConsecutive(int left, int right){
        return left == (right - 1);
    }

    public static boolean arePairsConsecutive(List<Pair<Integer,Integer>> pairs){
        for(int i = 0; i < pairs.size() - 1; i++)
            if(!arePairsConsecutive(pairs.get(i), pairs.get(i + 1)))
                return false;
        return true;
    }


    public static boolean arePairsConsecutive(Pair<Integer, Integer> left, Pair<Integer, Integer> right){
        return left.getRight() == right.getLeft();
    }

    public static List<Integer> occurrencesOfCharacterInArray(char[] searchArray, char searchCharacter){
        assert(searchArray.length>0);

        List<Integer> occurrences = Lists.newLinkedList();
        for(int i = 0;i<searchArray.length;i++){
            if(searchArray[i] == searchCharacter)
                occurrences.add(i);
        }
        return occurrences;
    }

    public static List<Pair<Integer,Integer>> findAllInstancesOfSubstringInString(String searchString, String substring, Pair<Integer,Integer> bounds){
        String string = substring(searchString,bounds);
        assert(StringUtils.isNoneBlank(substring,string));

        int lastIndex = 0;
        List<Pair<Integer,Integer>> listOfOccurrences = Lists.newLinkedList();
        while(lastIndex != -1){
            lastIndex = string.indexOf(substring,lastIndex);
            if(lastIndex != -1){
                int newIndex = lastIndex + substring.length();
                listOfOccurrences.add(Pair.of(lastIndex + bounds.getLeft(), newIndex + bounds.getLeft()));
                lastIndex = newIndex;
            }
        }
        return listOfOccurrences;
    }
}

它适用于提供的案例，但未经彻底测试。如果有任何错误请告诉我。

原始回复：

假设您正在搜索的字符串可以具有任意长度的标记（您的一些示例就是这样做的），那么：

您想要开始尝试将字符串分成与模式匹配的部分。一路寻找矛盾来减少你的搜索树。

当您开始处理时，您将选择字符串开头的 N 个字符。现在，去看看是否可以在字符串的其余部分中找到该子字符串。如果你不能，那么它不可能是一个解决方案。如果可以的话你的字符串看起来像这样

(N 个字符)<...>[(N 个字符)<...>] 其中任一 <...> 包含 0+ 个字符并且不一定是相同的子字符串。[] 中的内容可以重复的次数等于字符串中出现的次数（N 个字符）。

现在，您已经匹配了模式的第一个字母，您不确定模式的其余部分是否匹配，但您基本上可以重新使用此算法（经过修改）来询问字符串的 <...> 部分。

您会为 N = 1,2,3,4 执行此操作...有意义吗？

我将举一个例子（它不会涵盖所有情况，但希望能说明）注意，当我引用模式中的子字符串时，我将使用单引号，当我引用字符串 i' 的子字符串时，我将使用单引号。将使用双引号。

isMatch("ababac", "蓝绿蓝绿蓝白")

好的，“a”是我的第一个模式。对于 N = 1，我得到字符串“b”，搜索字符串中的“b”在哪里？ b绿绿b绿绿b绿白。

好的，此时该字符串可能与模式“a”的“b”匹配。让我们看看是否可以对模式“b”做同样的事情。从逻辑上讲，“b”必须是整个字符串“luegreen”（因为它被挤压在两个连续的“a”模式之间），然后我在第二个和第三个“a”之间检查。是的，它的“蓝绿”。

好的，到目前为止，我已经匹配了除模式中的“c”之外的所有内容。简单的情况，就是字符串的其余部分。它匹配。

这基本上是在编写 Perl 正则表达式解析器。ababc = (.+)(.+)(\1)(\2)(.+)。所以你只需要把它转换成 Perl 正则表达式