Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
921 views
in Technique[技术] by (71.8m points)

algorithm - Java: Longest common subsequence

I have following code:

public class LCS1 {

    public static String lcs(String a, String b) {
        String x;
        String y;

        int alen = a.length();
        int blen = b.length();
        if (alen == 0 || blen == 0) {
            return "";
        } else if (a.charAt(alen - 1) == b.charAt(blen - 1)) {
            return lcs(a.substring(0, alen - 1), b.substring(0, blen - 1));
        } else {
            x = lcs(a, b.substring(0, blen - 1));
            y = lcs(a.substring(0, alen - 1), b);
        }
        return (x.length() > y.length()) ? x : y;
    }

    public static void main(String[] args) {    
        String a = "computer";
        String b = "houseboat";
        System.out.println(lcs(a, b));    
    }
}

It should return "out" but an empty string returns what is problem?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

I'm not sure, but I think, the lines

else if (a.charAt(alen-1)==b.charAt(blen-1)){
  return lcs(a.substring(0,alen-1),b.substring(0,blen-1));
}

should be changed to

else if (a.charAt(alen-1)==b.charAt(blen-1)){
  return lcs(a.substring(0,alen-1),b.substring(0,blen-1)) + a.charAt(alen-1);
}

Otherwise no concatenation of strings takes place and only "" is returned.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...