Сохранение всех возможных LCS в списке и возврат в конце - PullRequest
Новая
       39

Сохранение всех возможных LCS в списке и возврат в конце

0 голосов
/ 08 февраля 2019

Я хочу вернуть все LCS, найденные в конце, в виде списка

Я могу напечатать все возможные LCS 

public static void main(String[] args) {
        String str1 = "abcbdab";
        String str2 = "bdcaba";
        int[][] arr = new int[str1.length()+1][str2.length()+1];
        for(int i = 0;i<arr.length;i++) {
            arr[i][0] = 0;

        }
        for(int i = 0;i<arr[0].length;i++) {
            arr[0][i] = 0;

        }
        System.out.println("Priting all the possible subsequences");
        findAllLCS(arr,str1, str2, r,c,"",new HashSet<String>());
    }


     public static void findAllLCS(int[][] arr, String str1,String str2,int r, int c, String str,Set<String> set) {
            if(r<=0 || c<=0) {
                if(!set.contains(str)) {
                    System.out.println(str);
                    set.add(str);
                }
                return;
            }
            if(str1.charAt(r-1)==str2.charAt(c-1)) {
                str =Character.toString(str1.charAt(r-1))+str;
                findAllLCS( arr, str1,str2,  r-1,  c-1, str,set); 
            }
            else {
                if(arr[r-1][c]==arr[r][c-1]) {
                    findAllLCS( arr, str1, str2, r-1,  c, str,set);
                    findAllLCS( arr,str1,str2,  r,  c-1, str,set);
                }
                else {
                    if(arr[r-1][c]>arr[r][c-1])
                        findAllLCS( arr,str1, str2,  r-1,  c, str,set);
                    else
                        findAllLCS( arr,str1, str2,  r,  c-1, str,set);
                }
            }
        }

Тип возврата должен быть List, который возвращает толькосписок всех возможных LCS

...