Dada una lista de cadenas:
ArrayList<String> strList = new ArrayList<String>(); strList.add("Mary had a little lamb named Willy"); strList.add("Mary had a little ham"); strList.add("Old McDonald had a farm named Willy"); strList.add("Willy had a little dog named ham"); strList.add("(abc)"); strList.add("(xyz)"); strList.add("Visit Target Store"); strList.add("Visit Walmart Store"); Esto debería producir la salida en forma de HashMap<String, Integer> prefixMap y suffixMap :
PREFIJO :
Mary had a -> 2 Mary had a little -> 2 ( -> 2 Visit -> 2SUFIJO :
named Willy -> 2 ham -> 2 ) -> 2 Store -> 2Hasta ahora, puedo generar un prefijo que está presente en todos los elementos de la lista usando el siguiente código:
public static final int INDEX_NOT_FOUND = -1; public static String getAllCommonPrefixesInList(final String... strs) { if (strs == null || strs.length == 0) { return EMPTY_STRING; } final int smallestIndexOfDiff = getIndexOfDifference(strs); if (smallestIndexOfDiff == INDEX_NOT_FOUND) { // All Strings are identical if (strs[0] == null) { return EMPTY_STRING; } return strs[0]; } else if (smallestIndexOfDiff == 0) { // No common initial characters found, return empty String return EMPTY_STRING; } else { // Common initial character sequence found, return sequence return strs[0].substring(0, smallestIndexOfDiff); } } public static int getIndexOfDifference(final CharSequence... charSequence) { if (charSequence == null || charSequence.length <= 1) { return INDEX_NOT_FOUND; } boolean isAnyStringNull = false; boolean areAllStringsNull = true; final int arrayLen = charSequence.length; int shortestStrLen = Integer.MAX_VALUE; int longestStrLen = 0; // Find the min and max string lengths - avoids having to check that we are not exceeding the length of the string each time through the bottom loop. for (int i = 0; i < arrayLen; i++) { if (charSequence[i] == null) { isAnyStringNull = true; shortestStrLen = 0; } else { areAllStringsNull = false; shortestStrLen = Math.min(charSequence[i].length(), shortestStrLen); longestStrLen = Math.max(charSequence[i].length(), longestStrLen); } } // Deals with lists containing all nulls or all empty strings if (areAllStringsNull || longestStrLen == 0 && !isAnyStringNull) { return INDEX_NOT_FOUND; } // Handle lists containing some nulls or some empty strings if (shortestStrLen == 0) { return 0; } // Find the position with the first difference across all strings int firstDiff = -1; for (int stringPos = 0; stringPos < shortestStrLen; stringPos++) { final char comparisonChar = charSequence[0].charAt(stringPos); for (int arrayPos = 1; arrayPos < arrayLen; arrayPos++) { if (charSequence[arrayPos].charAt(stringPos) != comparisonChar) { firstDiff = stringPos; break; } } if (firstDiff != -1) { break; } } if (firstDiff == -1 && shortestStrLen != longestStrLen) { // We compared all of the characters up to the length of the // shortest string and didn't find a match, but the string lengths // vary, so return the length of the shortest string. return shortestStrLen; } return firstDiff; } Sin embargo, mi objetivo es incluir cualquier prefijo / sufijo con al menos 2+ o más ocurrencias en el mapa resultante.
¿Cómo se puede lograr esto con Java ?
Creo que la solución proporcionada por @Abhinav debería funcionar con HashMap. Aquí publicaré la solución utilizando una implementación simple de Trie en Java (con algunas personalizaciones, como agregar freq en Trie Node).
ArrayList<String> strList = new ArrayList<String>(); strList.add("Mary had a little lamb named Willy"); strList.add("Mary had a little ham"); strList.add("Old McDonald had a farm named Willy"); strList.add("Willy had a little dog named ham"); strList.add("( abc )"); strList.add("( xyz )"); strList.add("Visit Target Store"); strList.add("Visit Walmart Store"); TNode root = new TNode(""); int maxFreq = 1; for(String sentence : strList) { TNode currentNode = root; String[] words = sentence.split(" "); // Assuming space character is the delimiter for(String word: words) { if(currentNode.children.containsKey(word)) { currentNode.children.get(word).freq += 1; maxFreq = Math.max(maxFreq, currentNode.children.get(word).freq); } else { TNode c = new TNode(word); c.freq = 1; currentNode.children.put(word, c); } currentNode = currentNode.children.get(word); } } Map<String, Integer> result = new HashMap<String, Integer>(); Queue<NodeWithPrefix> queue = new LinkedList<NodeWithPrefix>(); for(TNode node : root.children.values()){ NodeWithPrefix nwp = new NodeWithPrefix(node); nwp.prefix = ""; queue.add(nwp); } while(!queue.isEmpty()) { NodeWithPrefix item = queue.poll(); if(item.node.freq == maxFreq) { result.put(item.prefix + " " + item.node.value, item.node.freq); } for(TNode child : item.node.children.values()) { NodeWithPrefix nwp = new NodeWithPrefix(child); nwp.prefix = item.prefix + " " + item.node.value; queue.add(nwp); } } return result;Aquí hay otras 2 clases requeridas para este algoritmo:
class NodeWithPrefix { String prefix; TNode node; public NodeWithPrefix(TNode node){ this.node = node; } } class TNode { String value; int freq = 0; Map<String, TNode> children; public TNode(String value){ this.value = value; children = new HashMap<String, TNode>(); } }La salida es para el prefijo: (para el postfijo debe ser similar, solo necesita construir el Trie al revés)
{ Mary had=2, Mary had a=2, Visit=2, (=2, Mary had a little=2, Mary=2}Aquí estoy usando un BFS para recuperar todas las subcadenas que tienen una frecuencia igual a maxFreq en el Trie. Podemos ajustar la condición del filtro según la necesidad. Puede hacer el DFS aquí también. Otra consideración es que podemos agregar un prefijo en la propia clase TNode, prefiero mantenerlo separado en otra clase.