шаблона согласования интервью Q

Question

Я был недавно в интервью, и они задавали мне следующий вопрос:

Написать функцию возвращает истину, если строка соответствует шаблону, ложному иначе

Pattern : 1 символ за единицу, (аги), вход: пробела строка

Это было мое решение первой задачи:

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 

Я написал решение BruteForce (генерирующую все возможные расколы входной строки размера letters.length и проверки, в свою очередь против isMatch), но интервьюер сказал, что это не является оптимальным.

Я понятия не имею, как решить эту часть проблемы, возможно ли это, или я что-то упускаю?

Они искали что-то с временной сложностью O(M x N^C), где M - длина рисунка, а N - длина ввода, C - некоторая константа.

Разъяснения

• Я не ищу для регулярного выражения решения, даже если он работает.
• Я не ищу наивное решение, которое генерирует все возможные расщепления и проверяет их, даже с оптимизацией, поскольку это всегда будет экспоненциальным временем.

Answer 1

ОБНОВЛЕНИЕ: Вот мое решение. Основывался на объяснении, которое я сделал раньше.

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; 
    } 
} 

Он работает с установленными шкафами, но не подвергся тщательной проверке. Дайте мне знать, есть ли ошибки.

ORIGINAL РЕПЛИКА:

Если предположить, что строки вы искомая может иметь произвольную длину маркеров (которые некоторые из ваших примеров делают), то:

Вы хотите начать пытаться разбить строку на части, которые соответствуют шаблон. Ищете противоречия на пути к сокращению вашего дерева поиска.

Когда вы начнете обрабатывать, вы должны выбрать N символов начала строки. Теперь перейдите и посмотрите, сможете ли вы найти эту подстроку в остальной части строки. Если вы не можете, то это не может быть решением.Если вы можете, то ваша строка выглядит примерно так:

(N символов) < ...> [(N символов) < ...>] где либо один из < ...> содержит 0+ символов и арен. 't обязательно одна и та же подстрока. И что внутри [] может повторяться несколько раз, равное количеству раз (N символов), появляется в строке.

Теперь у вас есть первая буква вашего шаблона, вы не уверены, соответствует ли остальная часть шаблона, но вы можете в принципе повторно использовать этот алгоритм (с модификациями) для опроса < ...> частей Струна.

Вы бы сделали это для N = 1,2,3,4 ... Имеют смысл?

Я опишу пример (который не охватывает все случаи, но, надеюсь, иллюстрирует). Обратите внимание, что когда я имею в виду подстроки в шаблоне, я буду использовать одинарные кавычки и когда я имею в виду подстроки в строке я буду использовать двойные кавычки.

isMatch ("ababac", "bluegreenbluegreenbluewhite")

Ok, 'а' мой первый рисунок. для N = 1, я получаю строку «b» где «b» в строке поиска? b luegreen b luegreen b luewhite.

Итак, в этот момент эта строка MIGHT соответствует «b», являющемуся образцом «a». Давайте посмотрим, можем ли мы сделать то же самое с шаблоном «b». Логически, «b» ДОЛЖЕН быть всей строкой «luegreen» (потому что она сжимается между двумя последовательными «a» образцами), тогда я беру счет между 2-м и 3-м 'a'. YUP, его "luegreen".

Хорошо, до сих пор я сопоставлял все, кроме 'c' моего шаблона. Легкий случай, остальная часть строки. Это соответствует.

В основном это написанный парсер регулярного выражения Perl. ababc = (. +) (. +) (\ 1) (\ 2) (. +). Таким образом, вам просто нужно преобразовать его в регулярное выражение Perl.

Answer 2

Возможно оптимизировать решение обратного отслеживания. Вместо того, чтобы сначала генерировать все расщепления, а затем проверить, что он действительный, мы можем проверить его «на лету». Предположим, что мы уже разделили префикс (с длиной p) исходной строки и сопоставили i символов из шаблона. Давайте посмотрим на символ i + 1.

1. Если есть строка в префиксе, который соответствует i + 1 письму, мы должны просто проверить, что подстрока начинается с позиции p + 1 равна ей. Если это так, мы переходим к i + 1 и p + the length of this string. В противном случае мы можем убить эту ветку.

2. Если такой строки нет, мы должны попробовать все подстроки, которые начинаются в позиции p + 1 и заканчиваются где-то после нее.

Мы также можем использовать следующую идею, чтобы уменьшить количество филиалов в вашем решении: мы можем оценить длину суффикса образца, который не был обработан еще (мы знаем длину для писем, уже стоят за некоторые строки, и мы знаем тривиальную нижнюю границу длины строки для любой буквы в шаблоне (это 1)).Это позволяет нам убить ветку, если оставшаяся часть исходной строки слишком короткая, чтобы соответствовать остальной части шаблона.

Это решение все еще имеет экспоненциальную временную сложность, но может работать намного быстрее, чем генерировать все расщепления, потому что недействительные решения могут быть выброшены намного раньше, поэтому число достижимых состояний может значительно сократиться.

Answer 3

Вы можете улучшить грубую силу, предварительно допуская длины токенов и проверяя, что сумма длин токенов равна длине тестовой строки. Это будет быстрее, чем сопоставление шаблонов каждый раз. Тем не менее, очень медленно, поскольку количество уникальных жетонов увеличивается.

Answer 4

Я чувствую, что это обман, и я не уверен, что группа захвата и неохотный квантификатор подойдут правильно. Или, может быть, они ищут, можете ли вы признать, что из-за того, как работают кванторы, сопоставление неоднозначно.

boolean matches(String s, String pattern) { 
    StringBuilder patternBuilder = new StringBuilder(); 
    Map<Character, Integer> backreferences = new HashMap<>(); 
    int nextBackreference = 1; 

    for (int i = 0; i < pattern.length(); i++) { 
     char c = pattern.charAt(i); 

     if (!backreferences.containsKey(c)) { 
      backreferences.put(c, nextBackreference++); 
      patternBuilder.append("(.*?)"); 
     } else { 
      patternBuilder.append('\\').append(backreferences.get(c)); 
     } 
    } 

    return s.matches(patternBuilder.toString()); 
} 

Answer 5

Вот пример фрагмент моего кода:

public static final boolean isMatch(String patternStr, String input) { 
    // Initial Check (If all the characters in the pattern string are unique, degenerate case -> immediately return true) 
    char[] patt = patternStr.toCharArray(); 
    Arrays.sort(patt); 
    boolean uniqueCase = true; 
    for (int i = 1; i < patt.length; i++) { 
     if (patt[i] == patt[i - 1]) { 
      uniqueCase = false; 
      break; 
     } 
    } 
    if (uniqueCase) { 
     return true; 
    } 
    String t1 = patternStr; 
    String t2 = input; 
    if (patternStr.length() == 0 && input.length() == 0) { 
     return true; 
    } else if (patternStr.length() != 0 && input.length() == 0) { 
     return false; 
    } else if (patternStr.length() == 0 && input.length() != 0) { 
     return false; 
    } 
    int count = 0; 
    StringBuffer sb = new StringBuffer(); 
    char[] chars = input.toCharArray(); 
    String match = ""; 
    // first read for the first character pattern 
    for (int i = 0; i < chars.length; i++) { 
     sb.append(chars[i]); 
     count++; 
     if (!input.substring(count, input.length()).contains(sb.toString())) { 
      match = sb.delete(sb.length() - 1, sb.length()).toString(); 
      break; 
     } 
    } 
    if (match.length() == 0) { 
     match = t2; 
    } 
    // based on that character, update patternStr and input string 
    t1 = t1.replace(String.valueOf(t1.charAt(0)), ""); 
    t2 = t2.replace(match, ""); 
    return isMatch(t1, t2); 
} 

основном я решил разобрать первую строку шаблона и определить, имеются ли какие-либо соответствующие символы в строке шаблона. Например, в «aab» «a» используется дважды в строке шаблона, и поэтому «a» не может сопоставляться с чем-то другим. В противном случае, если в строке нет соответствующих символов, таких как «abc», не имеет значения, какова наша входная строка, так как шаблон уникален, и поэтому не имеет значения, к какому соответствует каждый символ шаблона (дегенеративный случай).

Если в строке шаблона есть соответствующие символы, я бы начал проверять соответствие каждой строки. К сожалению, не зная разделителя, я не знаю, как долго будет каждая строка. Вместо этого я просто решил разобрать 1 символ за раз и проверить, содержат ли другие части строки одну строку и продолжают добавлять символы в буферную букву буквой до тех пор, пока в строке ввода не будет найдена строка буфера. Как только я определил строку, теперь она находится в буфере, я просто удалю все совпадающие строки во входной строке и шаблон символа из строки шаблона, а затем рекурсия.

Извините, если мои объяснения были не очень ясными, я надеюсь, что мой код может быть ясен.