java - sort - Entrevista de coincidencia de patrones Q

selection sort algorithm java

Question

Hace poco estuve en una entrevista y me hicieron la siguiente pregunta:

Escriba una función para devolver verdadero si una cadena coincide con un patrón, de lo contrario, falso

Patrón: 1 carácter por elemento, (az), entrada: cadena delimitada por espacios

Esta fue mi solución para el primer problema:

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

La siguiente parte del problema me dejó perplejo:

Sin delimitadores en la entrada, escriba la misma función.

p.ej:

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

Escribí una solución de fuerza bruta (generando todas las posibles divisiones de la cadena de entrada de letters.length de letters.length y comprobación a su vez contra isMatch ), pero el entrevistador dijo que no era óptima.

No tengo idea de cómo resolver esta parte del problema, ¿es esto posible o me estoy perdiendo algo?

Estaban buscando algo con una complejidad de tiempo de O(M x N ^ C) , donde M es la longitud del patrón y N es la longitud de la entrada, C es algo constante.

Aclaraciones

• No estoy buscando una solución de expresiones regulares, incluso si funciona.
• No estoy buscando la solución ingenua que genera todas las divisiones posibles y las comprueba, incluso con optimización, ya que siempre será un tiempo exponencial.

Answer 1

ACTUALIZACIÓN: Aquí está mi solución. Lo basé en la explicación que hice antes.

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

Funciona con los casos proporcionados, pero no está completamente probado. Déjame saber si hay algún error.

RESPUESTA ORIGINAL:

Asumiendo que la cadena que está buscando puede tener tokens de longitud arbitraria (como lo hacen algunos de sus ejemplos):

Quieres comenzar a intentar dividir tu cadena en partes que coincidan con el patrón. Buscando contradicciones en el camino para reducir su árbol de búsqueda.

Cuando empieces a procesar, vas a seleccionar N caracteres del principio de la cadena. Ahora, ve a ver si puedes encontrar esa subcadena en el resto de la cadena. Si no puedes, entonces no puede ser una solución. Si puede, entonces su cadena se ve algo como esto

(N caracteres) <...> [(N caracteres) <...>] donde uno de los <...> contiene 0+ caracteres y no es necesariamente la misma subcadena. Y lo que está dentro de [] podría repetirse un número de veces igual al número de veces (N caracteres) que aparecen en la cadena.

Ahora, tiene la primera letra de su patrón coincidente, no está seguro de si el resto del patrón coincide, pero básicamente puede reutilizar este algoritmo (con modificaciones) para interrogar las partes <...> de la cadena.

Harías esto para N = 1,2,3,4 ... ¿Tiene sentido?

Trabajaré un ejemplo (que no cubre todos los casos, pero espero que lo ilustre) Nota: cuando me refiero a las subcadenas en el patrón usaré comillas simples y cuando me refiero a las subcadenas de la cadena i '' Usaré comillas dobles.

isMatch ("ababac", "bluegreenbluegreenbluewhite")

Ok, ''a'' es mi primer patrón. para N = 1 obtengo la cadena "b" donde está "b" en la cadena de búsqueda? b luegreen b luegreen b luewhite.

Bien, en este punto, esta cadena PUEDE coincidir con "b" como patrón ''a''. Veamos si podemos hacer lo mismo con el patrón ''b''. Lógicamente, ''b'' DEBE ser toda la cadena "luegreen" (debido a que se comprime entre dos patrones ''a'' consecutivos), luego me inscribo entre la segunda y la tercera ''a''. YUP, su "luegreen".

Ok, hasta ahora he emparejado todos menos la ''c'' de mi patrón. Caso fácil, es el resto de la cadena. Concuerda.

Esto es básicamente escribir un analizador de expresiones regulares de Perl. ababc = (. +) (. +) (/ 1) (/ 2) (. +). Así que solo hay que convertirlo en una expresión regular de Perl

Answer 2

Aquí hay un fragmento de mi código de muestra:

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

Básicamente, decidí analizar primero la cadena del patrón y determinar si hay caracteres coincidentes en la cadena del patrón. Por ejemplo, en "aab", "a" se usa dos veces en la cadena del patrón y por lo tanto "a" no se puede asignar a otra cosa. De lo contrario, si no hay caracteres coincidentes en una cadena como "abc", no importará cuál sea nuestra cadena de entrada ya que el patrón es único y, por lo tanto, no importa a qué coincida cada carácter de patrón (caso degenerativo).

Si hay caracteres coincidentes en la cadena del patrón, entonces comenzaría a verificar con qué coincide cada cadena. Desafortunadamente, sin conocer el delimitador, no sabría cuánto tiempo duraría cada cuerda. En su lugar, simplemente decidí analizar 1 carácter a la vez y comprobar si las otras partes de la cadena contienen la misma cadena y continuar agregando caracteres a la letra del búfer por letra hasta que la cadena del búfer no se encuentre en la cadena de entrada. Una vez que haya determinado la cadena, ahora está en el búfer, simplemente eliminaré todas las cadenas coincidentes en la cadena de entrada y el patrón de caracteres de la cadena del patrón y luego repetiré.

Disculpas si mi explicación no fue muy clara, espero que mi código pueda ser claro.

Answer 3

Es posible optimizar una solución de backtracking. En lugar de generar todas las divisiones primero y luego verificar que es válida, podemos verificarla "al vuelo". Supongamos que ya hemos dividido un prefijo (con longitud p ) de la cadena inicial y hemos hecho coincidir los caracteres i del patrón. Echemos un vistazo al carácter i + 1 .

1. Si hay una cadena en el prefijo que corresponde a la letra i + 1 , deberíamos verificar que una subcadena que comienza en la posición p + 1 es igual a esta. Si es así, simplemente procedemos a i + 1 y p + the length of this string . De lo contrario, podemos matar a esta rama.

2. Si no hay tal cadena, deberíamos probar todas las subcadenas que comienzan en la posición p + 1 y terminan en algún lugar después de ella.

También podemos usar la siguiente idea para reducir el número de sucursales en su solución: podemos estimar la longitud del sufijo del patrón que aún no se ha procesado (sabemos la longitud de las letras que ya representan algunas cadenas, y conocemos un límite inferior trivial de la longitud de una cadena para cualquier letra en el patrón (es 1)). Nos permite matar una rama si la parte restante de la cadena inicial es demasiado corta para coincidir con el resto del patrón.

Esta solución aún tiene una complejidad de tiempo exponencial, pero puede funcionar mucho más rápido que generar todas las divisiones, ya que las soluciones no válidas se pueden desechar mucho antes, por lo que el número de estados alcanzables puede reducirse significativamente.

Answer 4

Podría mejorar la fuerza bruta si primero asume las longitudes del token y verifique que la suma de las longitudes del token sea igual a la longitud de la cadena de prueba. Eso sería más rápido que la coincidencia de patrones cada vez. Sin embargo, sigue siendo muy lento a medida que aumenta el número de tokens únicos.

Answer 5

Siento que esto es un engaño, y no estoy convencido de que el grupo de captura y el cuantificador reacio hagan lo correcto. O tal vez están buscando para ver si puedes reconocer eso, debido a cómo funcionan los cuantificadores, la comparación es ambigua.

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