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\$
  • \$\begingroup\$ Suggestion: use a random word generator for the test cases. \$\endgroup\$ – Eyal Feb 14 '16 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\$ – Alexis Wilke Feb 14 '16 at 21:07
  • \$\begingroup\$ Surely you could have come up with more test cases and discovered that your code doesn't work. \$\endgroup\$ – 200_success Feb 14 '16 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 Feb 15 '16 at 8:04
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
    \$\begingroup\$ Please check your comment in 2. IMHO for input of "aabb" and "abbbb" the answer should be "abb", not "aab". \$\endgroup\$ – CiaPan Feb 14 '16 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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