分離複合詞和簡單詞

Question

我知道這個問題可能是最好的與DP服務，但我想知道是否有可能做到這一點與遞歸作爲蠻力的方式。給定一組單詞，比如{「sales」，「person」，「salesperson」}，確定哪些單詞是複合詞（即它是列表中的兩個或更多單詞的組合）。所以在這種情況下，銷售員=銷售員+人員，並且是複合的。

我根據我的答案很大程度上掉這個問題的：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; 
} 

這裏的問題是，現在是，雖然它成功的找到了營業員的合成詞，它也將確定的銷售和人作爲複合詞。此代碼是否可以修改以便該遞歸解決方案可以工作？我很難想出如何輕鬆地做到這一點。

Answer 1

這裏是遞歸性

解決

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

就這樣稱呼它：

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