Trennende Verbindung und einfache Wörter

Question

Ich weiß, dass dieses Problem wahrscheinlich am besten mit DP gedient wird, aber ich fragte mich, ob es möglich war, es mit der Rekursion als eine rohe Kraftweise zu machen.

Geben Sie eine Wortgruppe an, sagen Sie {"sales", "person", "salesperson"}, bestimmen Sie, welche Wörter zusammengehören (also die Kombination aus 2 oder mehr Wörtern in der Liste). Also in diesem Fall, Verkäufer = Umsatz + Person, und ist zusammengesetzt.

ich anhand meiner Antwort stark dieses Problems ab: http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/

public static void main(String args[]) throws Exception { 

    String[] test = { "salesperson", "sales", "person" }; 
    String[] output = simpleWords(test); 


    for (int i = 0; i < output.length; i++) 
     System.out.println(output[i]); 
} 

static String[] simpleWords(String[] words) { 
    if (words == null || words.length == 0) 
     return null; 

    ArrayList<String> simpleWords = new ArrayList<String>(); 

    for (int i = 0; i < words.length; i++) { 
     String word = words[i]; 
     Boolean isCompoundWord = breakWords(words, word); 

     if (!isCompoundWord) 
      simpleWords.add(word); 
    } 

    String[] retVal = new String[simpleWords.size()]; 
    for (int i = 0; i < simpleWords.size(); i++) 
     retVal[i] = simpleWords.get(i); 

    return retVal; 

} 

static boolean breakWords(String[] words, String word) { 
    int size = word.length(); 

    if (size == 0) return true; 

    for (int j = 1; j <= size; j++) { 

     if (compareWords(words, word.substring(0, j)) && breakWords(words, word.substring(j, word.length()))) { 
      return true; 
     } 
    } 

    return false; 
} 

static boolean compareWords(String[] words, String word) { 
    for (int i = 0; i < words.length; i++) { 
     if (words[i].equals(word)) 
      return true; 
    } 
    return false; 
} 

Das Problem ist jetzt, dass, während es Verkäufer als zusammengesetztes Wort erfolgreich identifiziert, wird es auch Umsatz und Person als zusammengesetztes Wort identifizieren. Kann dieser Code überarbeitet werden, damit diese rekursive Lösung funktioniert? Ich habe Probleme damit zu kommen, wie ich das leicht machen kann.

Answer 1

Hier ist eine Lösung mit Rekursivität

public static String[] simpleWords(String[] data) { 
    List<String> list = new ArrayList<>(); 
    for (String word : data) { 
     if (!isCompound(data, word)) { 
      list.add(word); 
     } 
    } 
    return list.toArray(new String[list.size()]); 
} 

public static boolean isCompound(String[] data, String word) { 
    return isCompound(data, word, 0); 
} 

public static boolean isCompound(String[] data, String word, int iteration) { 
    if (data == null || word == null || word.trim().isEmpty()) { 
     return false; 
    } 
    for (String str : data) { 
     if (str.equals(word) && iteration > 0) { 
      return true; 
     } 
     if (word.startsWith(str)) { 
      String subword = word.substring(str.length()); 
      if (isCompound(data, subword, iteration + 1)) { 
       return true; 
      } 
     } 
    } 
    return false; 
} 

es einfach wie folgt aufrufen:

String[] data = {"sales", "person", "salesperson"}; 
System.out.println(Arrays.asList(simpleWords(data)));