Longest Common Prefix string

Question

Below is my recursive approach to finding the longest common prefix to a set of strings.

package recursion;

public class LongestCommonPrefix {
    public static String longestCommonPrefix(String[] str) {
        String finalStr = longestCommonPrefixHelper(str,"");
        return finalStr;
    }
    public static String longestCommonPrefixHelper(String[] str,String prefix) {
        if(str.length==0) {
            return prefix;
        }
        System.out.println("Prefix is "+prefix);
        for(int i=0;i<str.length;i++) {
            if(str[i].equals("")) {
                return prefix;
            }
        }
        String ch = str[0].substring(0, 1);
        for(int i=0;i<str.length;i++) {
            if(!str[i].substring(0, 1).equals(ch)) {

                return prefix;
            }
            else if(str[i].length()>1)
                str[i] = str[i].substring(1, str[i].length());
            else
                str[i]="";
        }
        prefix= prefix+ch;
        longestCommonPrefixHelper(str, prefix);
        return prefix;
    }

    public static void display(String[] s) {
        for(int i=0;i<s.length;i++) {
            System.out.print(s[i]+" ");
        }
    }

    public static void main(String[] args) {
        String[] s = {"Sujit","Suhail","Suit","Susan"};

        System.out.println(longestCommonPrefix(s));
    }
}

For some reason, I do not get the correct output. There happens to be a minor thing which I have missed. Any form of help is much appreciated. Thanks in advance

Naor Tedgi · Accepted Answer · 2018-12-17T20:21:48.263

change this

prefix= prefix+ch;
longestCommonPrefixHelper(str, prefix);
return prefix;

to

return longestCommonPrefixHelper(str, prefix+ch);

you forget to call the recursion

  public class LongestCommonPrefix {
        public static String longestCommonPrefix(String[] str) {
            String finalStr = longestCommonPrefixHelper(str,"");
            return finalStr;
        }
        public static String longestCommonPrefixHelper(String[] str,String prefix) {
            if(str.length==0) {
                return prefix;
            }


            for(int i=0;i<str.length;i++) {
                if(str[i].equals("")) {
                    return prefix;
                }
            }

            String ch = str[0].substring(0, 1);
            for(int i=0;i<str.length;i++) {
                if(!str[i].substring(0, 1).equals(ch)) {
                    return prefix;
                }
                else if(str[i].length()>1)
                    str[i] = str[i].substring(1, str[i].length());
                else
                    str[i]="";
            }

            return longestCommonPrefixHelper(str, prefix+ch);
        }

        public static void display(String[] s) {
            for(int i=0;i<s.length;i++) {
                System.out.print(s[i]+" ");
            }
        }

        public static void main(String[] args) {
            String[] s = {"Sujit","Suhail","Suit","Susan"};

            System.out.println(longestCommonPrefix(s));
        }
    }

Thanks a lot! Much appreciated – Sunit Mishra Dec 17 '18 at 21:32 — Sunit Mishra, Dec 17 '18 at 21:32

Longest Common Prefix string

1 Answers1