Разделительный состав и простые слова

Question

Я знаю, что эта проблема, вероятно, лучше всего подходит для DP, но мне было интересно, можно ли это сделать с рекурсией как методом грубой силы.

Учитывая набор слов, скажем {"sales", "person", "salesperson"}, определите, какие слова являются составными (то есть, это комбинация из двух или более слов в списке). Таким образом, в этом случае продавец = sales + person, и является составным.

я основывался мой ответ сильно от этой проблемы: 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)));