分离复合词和简单词

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