Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is my function for determining the Longest Substring between two strings in Java.

public class Main {
    public static String longestSubstring(String str1, String str2){
        int row = str1.length();
        int col = str2.length();

        int[][] checker = new int[row][col];

        int max = 0;
        int r = 0;
        int c = 0;
        for(int i=0; i < row; i++){
            for(int j=0; j < col; j++){
                if(str1.charAt(i) == str2.charAt(j)){
                    if((i -1 > 0) && (j -1 >0)){
                        checker[i][j] = checker[i-1][j-1] +1;

                    }else{
                        checker[i][j]++;
                    }
                    max = checker[i][j];
                    r = i;
                    c = j;

                }else continue;
            }
        }
        StringBuilder sb = new StringBuilder();
        while(true){
            if(checker[r][c] == 0) break;
            sb.append(str1.charAt(r));
            r--;
            c--;
        }
        return sb.reverse().toString();

    }

    public static void main(String[] args) {
    // write your code here
        String str1 = "adedfrgyu";
        String str2 = "arvbfrgykset";

       String str3 = "aaaaaaatyuieo";
       String str4 = "aaaaaklui";

        System.out.println(longestSubstring(str1, str2));
    }
}

The code compiles, but wondering is the algorithm is correct. It passes all the test cases that I could make up.

share|improve this question
    
Suggestion: use a random word generator for the test cases. – Eyal Feb 14 at 20:35
    
If you want to make sure that all cases are covered by your tests (good testing requires such) then you need a tool that generate coverage data. You run your tests, then check coverage. If a case is never hit (i.e. an if() or else block never entered) then you've got a problem in your tests. – Alexis Wilke Feb 14 at 21:07
    
Surely you could have come up with more test cases and discovered that your code doesn't work. – 200_success Feb 14 at 23:22
    
(I think I'd like Longest Common Substring much better as a title, with in Java optional if the first tag is java.) – greybeard Feb 15 at 8:04
up vote 10 down vote accepted

I liked your DP approach and use of stringbuider instead of string.

  1. But, the code gives null pointer exception :

     Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at Test.longestSubstring(Test.java:157)
    at Test.main(Test.java:22)
    

for the input System.out.println(longestSubstring("aabb", "akk"));

The reason is that whenever the resultant substring starts from index 0, this code will throw a null pointer exception because checker[0][0] is 1(instead of 0), if the first characters match. Because, you're using if(checker[r][c] == 0) break; as the criteria to end the while loop. One solution is to have the while loop run for max number of times. Other approach is to use an array of 1 greater size i.e. int[][] checker = new int[row+1][col+1];

  1. Moreover, there is a small bug in this code :-

For input System.out.println(longestSubstring("aabb", "abbbb"));, the output is "bb". But, the right answer is "abb". Even for the given test cases,

  String str3 = "aaaaaaatyuieo";
   String str4 = "aaaaaklui";

    System.out.println(longestSubstring(str1, str2));

The answer should be "aaaaa". But, it returns "ui". The reason for that is that you should check if checker[i][j] is greater than max before assigning

max = checker[i][j];
r = i;
c = j;
  1. You need not write else continue; as the last statement in the loop.

Here is the complete code:-

    public static String longestSubstring(String str1, String str2){
    int row = str1.length();
    int col = str2.length();

    int[][] checker = new int[row+1][col+1];

    int max = 0;
    int r = 0;
    int c = 0;
    for(int i = 1; i <= row; i++){
        for(int j = 1; j <= col; j++){
            if(str1.charAt(i-1) == str2.charAt(j-1)){
                checker[i][j] = checker[i-1][j-1] +1;
                if(checker[i][j] > max){
                    max = checker[i][j];
                    r = i;
                    c = j;
                }
            }
        }
    }
    StringBuilder sb = new StringBuilder();
    while(true){
        if(checker[r][c] == 0) break;
        sb.append(str1.charAt(r-1));
        r--;
        c--;
    }
    return sb.reverse().toString();
}
share|improve this answer
1  
Please check your comment in 2. IMHO for input of "aabb" and "abbbb" the answer should be "abb", not "aab". – CiaPan Feb 14 at 22:38
    
Yes @CiaPan. You're right.. Thanks – maxomax Feb 14 at 22:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.