Учитывая список слов, как вы находите общие буквы, которые перекрываются

Question

У меня есть список слов. Вы проверяете суффикс первого слова на префикс следующего слова.

Например.

спокойный следующий танго дополнительные

{serene,next}= 2common letters {serene,tango}=0 {serene,extra}= 1 
{next,serene}= 0  {next,tango}= 1 {next,extra}= 3 
{tango,serene}=0  {tango,next}= 0 {tango,extra}= 0 
{extra,serene}=0  {extra,next}=0 {extra,tango}=0 

Вы также можете изменить порядок слов т.е. (следующий, спокойный), если перекрытие письмо оценка лучше этот путь

так что вы проверить перекрытие баллы с каждым словом и, наконец, верните список слов с максимальным счетом

По списку входных баллов 1 безмятежный, следующий, танго , Дополнительные = 1

Максимальное количество баллов, = 5, и список вывода вернулся бы следующее:

серин, рядом, дополнительный, танго

serene,next= 2common letters serene,tango=0 serene,extra= 1 
next,serene= 0     next,tango= 1 next,extra= 3 
tango,serene=0     tango,next= 0 tango,extra= 0 
extra,serene=0     extra,next=0 extra,tango=0 

Что такое лучший способ расчета балла перекрытия и вернуть максимальный список баллов с точки зрения сложности?

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

Answer 1

Вы можете добавить все буквы в списке, а затем сделать retainAll нравится:

String one="next", two="extra"; 
List<Character> oneList=new ArrayList<Character>(); 
for(Character c : one.toCharArray()) { 
    oneList.add(c); 
} 
List<Character> twoList=new ArrayList<Character>(); 
for(Character c : two.toCharArray()) { 
    twoList.add(c); 
} 
List<Character> finalList = new ArrayList<Character>(oneList); 
finalList.retainAll(twoList); 
System.out.print("There are "+finalList.size()+ " letters in common and they are : "); 
for(Character c: finalList){ 
    System.out.print(c+" "); 
} 

К сожалению, я не знаю, лучший способ преобразовать примитивный тип данных в списке, что с помощью Google Guava library или другой 3 участника API. Если вы хотите оптимизировать код, то смотрите на них.

Answer 2

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

Backtracking имеет плохую репутацию эффективности, но в текущем прецеденте я думаю, что он может быть использован, потому что мы можем остановить анализ, как только 2 слова имеют оценку 0. Поэтому я могу найти правильный максимальный балл 5 и лучшая последовательность в 11 операциях.

Код:

public class Overlap { 
    int[][] matrix; 
    int total; 
    int [] bestSeq; 
    String[] strings; 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] strings) { 
     // TODO code application logic here 
     Overlap overlap = new Overlap(strings); 
     int score = overlap.compute(); 
     System.out.println("Best score : " + score); 
     for (int i : overlap.bestSeq) { 
      System.out.print(" " + strings[i]); 
     } 
     System.out.println(" in " + overlap.total + " operations"); 

    } 

    public Overlap(String[] strings) { 
     this.strings = strings; 
     matrix = matrix(strings); 
     bestSeq = new int[strings.length]; 
    } 

    int compute() { 
     total = 0; 
     int[] sequence = new int[strings.length]; 
     for (int i=0; i < strings.length; i++) { 
      sequence[i] = i; 
     } 
     return this.bestSequence(-1, sequence, bestSeq); 
    } 

    static int findOverlap(String a, String b) { 
     int la = a.length(); 
     int l = Math.min(la, b.length()); 
     while (l > 0) { 
      if (a.substring(la - l).equals(b.substring(0, l))) { 
       return l; 
      } 
      l--; 
     } 
     return 0; 
    } 

    static int[][] matrix(String[] strings) { 
     int l = strings.length; 
     int[][] mx = new int[l][l]; 
     for (int i = 0; i < l - 1; i++) { 
      for (int j = i + 1; j < l; j++) { 
       mx[i][j] = findOverlap(strings[i], strings[j]); 
      } 
     } 
     return mx; 
    } 

    int bestSequence(int initial, int[] sequence, int[] best) { 
     total += 1; 
     int max = 0; 
     if (best.length != sequence.length) { 
      throw new java.lang.IllegalArgumentException(); 
     } 
     int l = sequence.length; 
     int[] newseq = new int[l - 1]; 
     int[] newbest = new int[l - 1]; 
     for (int i : sequence) { 
      int val = (initial == -1) ? 0 : matrix[initial][i]; 
      if ((val > 0) || (initial == -1)) { 
       int k = 0; 
       for (int j : sequence) { 
        if (j != i) { 
         newseq[k++] = j; 
        } 
       } 
       val += bestSequence(i, newseq, newbest); 
       if (val > max) { 
        max = val; 
        best[0] = i; 
        System.arraycopy(newbest, 0, best, 1, l - 1); 
       } 
      } 
     } 
     if (max == 0) { 
      System.arraycopy(sequence, 0, best, 0, l); 
     } 
     return max; 
    } 
} 

С аргументами serene next tango extra, он печатает:

Best score : 5 
serene next extra tango 
in 11 operations