die geringste Menge an Unter Worte

Question

Lösung von Dávid Horváth angepasst gibt es die größte kleinste Wort zurück:

import java.util.*; 

public class SubWordsFinder 
{ 
    private Set<String> words; 

    public SubWordsFinder(Set<String> words) 
    { 
     this.words = words; 
    } 

    public List<String> findSubWords(String word) throws NoSolutionFoundException 
    { 
     List<String> bestSolution = new ArrayList<>(); 
     if (word.isEmpty()) 
     { 
      return bestSolution; 
     } 
     long length = word.length(); 
     int[] pointer = new int[]{0, 0}; 
     LinkedList<int[]> pointerStack = new LinkedList<>(); 
     LinkedList<String> currentSolution = new LinkedList<>(); 
     while (true) 
     { 
      boolean backtrack = false; 
      for (int end = pointer[1] + 1; end <= length; end++) 
      { 
       if (end == length) 
       { 
        backtrack = true; 
       } 
       pointer[1] = end; 
       String wordToFind = word.substring(pointer[0], end); 
       if (words.contains(wordToFind)) 
       { 
        currentSolution.add(wordToFind); 
        if (backtrack) 
        { 
         if (bestSolution.isEmpty() || (currentSolution.size() <= bestSolution.size() && getSmallestSubWordLength(currentSolution) > getSmallestSubWordLength(bestSolution))) 
         { 
          bestSolution = new ArrayList<>(currentSolution); 
         } 
         currentSolution.removeLast(); 
        } else if (!bestSolution.isEmpty() && currentSolution.size() == bestSolution.size()) 
        { 
         currentSolution.removeLast(); 
         backtrack = true; 
        } else 
        { 
         int[] nextPointer = new int[]{end, end}; 
         pointerStack.add(pointer); 
         pointer = nextPointer; 
        } 
        break; 
       } 
      } 
      if (backtrack) 
      { 
       if (pointerStack.isEmpty()) 
       { 
        break; 
       } else 
       { 
        currentSolution.removeLast(); 
        pointer = pointerStack.removeLast(); 
       } 
      } 
     } 
     if (bestSolution.isEmpty()) 
     { 
      throw new NoSolutionFoundException(); 
     } else 
     { 
      return bestSolution; 
     } 
    } 

    private int getSmallestSubWordLength(List<String> words) 
    { 
     int length = Integer.MAX_VALUE; 

     for (String word : words) 
     { 
      if (word.length() < length) 
      { 
       length = word.length(); 
      } 
     } 

     return length; 
    } 

    public class NoSolutionFoundException extends Exception 
    { 
     private static final long serialVersionUID = 1L; 
    } 
} 

---

Ich habe ein String von regelmäßigen englischen Wörter in Kleinbuchstaben enthalten. Lassen Sie uns dies sagen String ist bereits in eine List aller möglichen Subworte zerlegt:

public List<String> getSubWords(String text) 
{ 
    List<String> words = new ArrayList<>(); 

    for (int startingIndex = 0; startingIndex < text.length() + 1; startingIndex++) 
    { 
     for (int endIndex = startingIndex + 1; endIndex < text.length() + 1; endIndex++) 
     { 
      String subString = text.substring(startingIndex, endIndex); 

      if (contains(subString)) 
      { 
       words.add(subString); 
      } 
     } 
    } 

    Comparator<String> lengthComparator = (firstItem, secondItem) -> 
    { 
     if (firstItem.length() > secondItem.length()) 
     { 
      return -1; 
     } 

     if (secondItem.length() > firstItem.length()) 
     { 
      return 1; 
     } 

     return 0; 
    }; 

    // Sort the list in descending String length order 
    Collections.sort(words, lengthComparator); 

    return words; 
} 

Wie finde ich die geringste Menge an Subworte, die den ursprünglichen String bilden?

Zum Beispiel:

String text = "updatescrollbar"; 
List<String> leastWords = getLeastSubWords(text); 
System.out.println(leastWords); 

Ausgang:

[update, scroll, bar] 

Ich bin nicht sicher, wie alle Möglichkeiten durchlaufen, da sie in Abhängigkeit von den gewählten Worten ändern. Ein Start wäre so etwas wie dieses:

public List<String> getLeastSubWords(String text) 
{ 
    String textBackup = text; 
    List<String> subWords = getSubWords(text); 
    System.out.println(subWords); 
    List<List<String>> containing = new ArrayList<>(); 

    List<String> validWords = new ArrayList<>(); 

    for (String subWord : subWords) 
    { 
     if (text.startsWith(subWord)) 
     { 
      validWords.add(subWord); 
      text = text.substring(subWord.length()); 
     } 
    } 

    // Did we find a valid words distribution? 
    if (text.length() == 0) 
    { 
     System.out.println(validWords.size()); 
    } 

    return null; 
} 

Hinweis:
Dies ist auf this Frage bezogen.

Answer 1

UPDATE: Der Algorithmus unten kann viel effizienter sein, wenn Sie den inneren foreach umkehren. In diesem Fall werden längere Wörter zuerst überprüft.

---

Dies ist eine typische Situation für einen Backtracking-Algorithmus.

Speichern Sie Ihre Worte in einem TreeSet und diesen Algorithmus implementieren:

1. Set Start- und End-Zeiger auf 0. Erstellen Sie einen Stapel, um vorherige Versionen des Zeigers zu speichern.

2. Generieren Sie Teilstrings vom Startzeiger, erhöhen Sie den Endzeiger und suchen Sie nach einem bekannten Wort. Wenn ein Wort gefunden, in einem Array gespeichert und die Wortlänge dem Startzeiger hinzugefügt wird, drücken Sie diesen Zeiger auf den Stack. Wenn kein bekanntes Wort gefunden wurde oder das letzte Zeichen erreicht wurde, setzen Sie die Start- und Endzeiger auf den vorherigen Wert, der vom Stapel ausgegeben wurde (Backtracking). Wiederholen Sie den 2. Schritt.

3. Um die geringste Anzahl an Unterworten zu finden, müssen Sie die vorherige beste Lösung speichern und die Anzahl der Wörter mit der Wortanzahl der aktuellen Lösung vergleichen.

Unten ist eine Beispielimplementierung. Es enthält einige Optimierungsexperimente: keine Rekursion, Rückverfolgung auf einer fehlerhaften Verzweigung usw. Sie können weitere Optimierungen hinzufügen (z. B. die Verfolgung von Startpositionen oder die Suche nach möglichen Startpositionen für Subwords), aber es ist wahrscheinlich unnötig, wenn der Parameter verwendet wird ist ein nicht zu langes Wort.

public class SubWordFinder { 

    private TreeSet<String> words = new TreeSet<String>(); 

    public SubWordFinder(Collection<String> words) { 
     this.words.addAll(words); 
    } 

    public List<String> findSubWords(String word) throws NoSolutionFoundException { 
     List<String> bestSolution = new ArrayList<String>(); 
     if (word.isEmpty()) { 
      return bestSolution; 
     } 
     long length = word.length(); 
     int[] pointer = new int[]{0, 0}; 
     LinkedList<int[]> pointerStack = new LinkedList<int[]>(); 
     LinkedList<String> currentSolution = new LinkedList<String>(); 
     while (true) { 
      boolean backtrack = false; 
      for (int end = pointer[1] + 1; end <= length; end++) { 
       if (end == length) { 
        backtrack = true; 
       } 
       pointer[1] = end; 
       String wordToFind = word.substring(pointer[0], end); 
       if (words.contains(wordToFind)) { 
        currentSolution.add(wordToFind); 
        if (backtrack) { 
         if (bestSolution.isEmpty() || currentSolution.size() < bestSolution.size()) { 
          bestSolution = new ArrayList<String>(currentSolution); 
         } 
         currentSolution.removeLast(); 
        } else if (!bestSolution.isEmpty() && currentSolution.size() == bestSolution.size()) { 
         currentSolution.removeLast(); 
         backtrack = true; 
        } else { 
         int nextStart = end; 
         int[] nextPointer = new int[]{nextStart, nextStart}; 
         pointerStack.add(pointer); 
         pointer = nextPointer; 
        } 
        break; 
       } 
      } 
      if (backtrack) { 
       if (pointerStack.isEmpty()) { 
        break; 
       } else { 
        currentSolution.removeLast(); 
        pointer = pointerStack.removeLast(); 
       } 
      } 
     } 
     if (bestSolution.isEmpty()) { 
      throw new NoSolutionFoundException(); 
     } else { 
      return bestSolution; 
     } 
    } 

    public class NoSolutionFoundException extends Exception { 

     private static final long serialVersionUID = 1L; 

    } 

} 

Tests:

public class SubWordFinderTest { 

    @Test 
    public void generalTest() throws SubWordFinder.NoSolutionFoundException { 
     List<String> words = new ArrayList<String>(); 
     words.add("ab"); 
     words.add("abc"); 
     words.add("cd"); 
     words.add("cde"); 
     words.add("de"); 
     words.add("e"); 
     SubWordFinder finder = new SubWordFinder(words); 
     assertEquals(new ArrayList<String>(), finder.findSubWords("")); 
     assertEquals(Arrays.asList("ab", "cde"), finder.findSubWords("abcde")); 
     assertEquals(Arrays.asList("cd", "cde"), finder.findSubWords("cdcde")); 
     assertEquals(Arrays.asList("abc", "cd"), finder.findSubWords("abccd")); 
     assertEquals(Arrays.asList("de", "e", "e", "e", "e"), finder.findSubWords("deeeee")); 
     try { 
      finder.findSubWords("ae"); 
      fail(); 
     } catch (SubWordFinder.NoSolutionFoundException e) { 
     } 
     try { 
      finder.findSubWords("abcccd"); 
      fail(); 
     } catch (SubWordFinder.NoSolutionFoundException e) { 
     } 
     try { 
      finder.findSubWords("abcdex"); 
      fail(); 
     } catch (SubWordFinder.NoSolutionFoundException e) { 
     } 
    } 

    @Test 
    public void dictionaryTest() throws IOException, SubWordFinder.NoSolutionFoundException { 
     String resourceDir = "/path_to_resources"; 
     InputStream inputStream = getClass().getResource(resourceDir + "/20k.txt").openStream(); 
     InputStreamReader inputStreamReader = new InputStreamReader(inputStream); 
     BufferedReader bufferedReader = new BufferedReader(inputStreamReader); 
     List<String> words = new ArrayList<String>(); 
     String line; 
     while ((line = bufferedReader.readLine()) != null) { 
      words.add(line); 
     } 
     SubWordFinder finder = new SubWordFinder(words); 
     assertEquals(Arrays.asList("bromide", "freshet"), finder.findSubWords("bromidefreshet")); 
    } 

} 

Answer 2

Das erfordert viele Szenario-Möglichkeiten.

Ihr Beispiel (updatescrollbar) hat bereits up date ate update scroll bar und ist immer noch ziemlich einfach, aber was ist, wenn Sie ein Wort haben, das als Subwörter, die Sie mit einem einzelnen Zeichen Möglichkeit am Ende der Zeichenfolge verlassen.

Um dies zu durchlaufen, müssen Sie mehrere Male über Ihre Liste von Unterworten iterieren, die aktuellste, am Ende gültige Version, die Ihrem Text entspricht, verfolgen und so lange wiederholen, bis Sie alle Variationen ausprobiert haben.

Sie können die Anzahl von Variationen zum Beispiel reduzieren, indem ein Algorithmus verwendet, der die verbleibende nimmt Raum Rechnung angepasst werden:

• Sortieren Sie Ihre Subworte auf Länge, und versuchen, den Text mit den längsten Wörter passen zuerst: Länge Unterwort möglich = Text -/- übereinstimmender Text. Dies würde ein contains verwenden, so dass der zu vergleichende Text immer noch vor und nach bereits übereinstimmenden Wörtern sein kann: Verwenden Sie ein Array für Ihren Text, so dass es einfacher ist, den übereinstimmenden Text zu verfolgen.