-1

我正在尝试实现 2 个字符串的最长公共子序列。我的方法与这里发布的有点不同。我接近解决方案，但问题不大。请帮我。

我的问题：期望输出：metalica 电流输出：etallica

我的代码是：

import java.util.ArrayList;
import java.util.Stack;

public class CommonSubS  {

public static void main(String[] args) {

   ArrayList<Character> ss = new ArrayList<>();
   String s1 = "metallicarules";
   String s2 = "rulmetallicales";
   ArrayList<ArrayList<Character>> one = new ArrayList<>();
   char[] first = s1.toCharArray();
   char[] second = s2.toCharArray();
   int j = 0;
   int current = 0;
   int mainIndex = 0;
   ArrayList<Character> sec = new ArrayList<>();

   // search for each char in second            
   for(int i = 0; i<second.length; i++)
   {    
       j = current;
       // search for each char in first
       while(j<first.length)
       {
           // if match found, add to the arraylist
           if(first[j] == second[i]){

               sec.add(first[j]);
               current = j+1;
               break;
           }
           else 
           {   // if different char occured in between,
               // save current arraylist in one
               // and go forward
               one.add(sec);
               sec = new ArrayList<>();
               j++; 
               current = 0;        
           }

       }
   }

   for(ArrayList<Character> s: one)
   {
       for(Character c: s)
       {
           System.out.print(c);
       }
       System.out.println();    
    }

  }
}

/*
 desired output: metallica
current output: etallica
*/

我知道还有其他方法，但我尝试使用简单的方法来实现。请指出问题。

4

2 回答 2

0

我仍然不确定您的算法是如何工作的，但我认为 的值j太快变得太大了。我每次都将您的else块更改为重置为 0，现在代码会产生所需的“metallica”输出。j

           else 
           {   // if different char occured in between,
               // save current arraylist in one
               // and go forward
               one.add(sec);
               sec = new ArrayList<>();
               j = 0; // Start checking from the beginning of the string
               current = 0;
               break; // This will exit the while loop and move on to the next value of i
           }
于 2013-03-19T04:27:06.843 回答
0

我认为问题在于您的 i 被递增并将第二个单词的 metala 中的 m 与第一个单词的最后一个 e 进行比较，因此下一次迭代它将从下一个字母开始，即 e （第二个单词的） ，这就是为什么你一开始没有得到 m 的原因。也许如果你每次结束一个公共子序列时都使用 i = i-1 。

于 2013-03-19T04:41:01.213 回答