5
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Suggestion: use a random word generator for the test cases. \$\endgroup\$
    – Eyal
    Commented Feb 14, 2016 at 20:35
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Feb 14, 2016 at 21:07
  • \$\begingroup\$ Surely you could have come up with more test cases and discovered that your code doesn't work. \$\endgroup\$ Commented Feb 14, 2016 at 23:22
  • \$\begingroup\$ (I think I'd like Longest Common Substring much better as a title, with in Java optional if the first tag is java.) \$\endgroup\$
    – greybeard
    Commented Feb 15, 2016 at 8:04

1 Answer 1

10
\$\begingroup\$

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();
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Please check your comment in 2. IMHO for input of "aabb" and "abbbb" the answer should be "abb", not "aab". \$\endgroup\$
    – CiaPan
    Commented Feb 14, 2016 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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