[Week Three] Programming Contest - Longest Prefix

General Discussion Off Topic
1

Welcome back to week three of the weekly programming contests! As always, you can find the rules and information on the contests Posted Here

This weeks challenge: is to implement the method: public static String prefix(String sentence). (The method and variable can be renamed) This method takes in a sentence (which is a String containing 2 or more words) and returns the longest common prefix of the words in that sentence. Case is irrelevant, If there are two longest prefixes, it should return an empty String, but since i did not specify this case beforehand, any output is fine.

Examples:

prefix(“Bob the bobbin builder”) -> “bob”
prefix(“Hello my name is Bob the happy lion”) -> “h”
prefix(“The quick brown dog jumped over a lazy fox”) -> “”
prefix(“There was a large patch of flowers growing near the flowing stream”) -> “flow”
prefix(“There once was a bird named Bill, who was friends with Bill the rhino”) -> “bill”
prefix(“I like to eat little puppies”) -> “li”

Imports will be allowed for this one!

Challenge Closes: Sunday 11/22/15

Good luck!

1 Like
2

Why not “the” for “The quick… the lazy fox” - looks like an exclusionary rule is in effect that needs to be clarified…

3

Sorry, my bad. I corrected the mistake in the example.

4

340 characters:

public static String p(String a){String[]b=a.split(" ");for(int i=0;i<b.length;i++)b[i]=b[i].toLowerCase();String c="";for(int g=0;g<b.length;g++)for(int h=0;h<b.length;h++){String d=b[g],e=b[h];int f=0;while (f++<d.length()&&g!=h&&f<=e.length()&&d.substring(0, f).equals(e.substring(0, f)));if(c.length()<--f)c=d.substring(0,f);}return c;}

Uncompressed:

public static String prefix(String all) {
    String[] words = all.split(" ");
    for (int i = 0; i < words.length; i++) {
        words[i] = words[i].toLowerCase();
    }
    String longest = "";
    for (int index1 : words) {
        for (int index2 : words) {
            String word1 = words[index1];
            String word2 = words[index2];
            int prefixLength = 0;
            while (prefixLength++ < word1.length() && !word1.equals(word2)
                   && prefixLength <= word2.length()
                   && word1.substring(0, prefixLength).equals(
                      word2.substring(0, prefixLength))) ;
            if (longest.length() < --prefixLength) longest = word1.substring(0, prefixLength);
        }
    }
    return longest;
}
5 
public static String p(String s){String l="",r[]=s.split(" "),z,y;for(int a=0,i=r.length,b,j;a<i;a++)for(b=a+1;b<i;){z=r[a];y=r[b++];for(j=l.length();j<Math.max(z.length(),y.length());j++)if(z.regionMatches(true,0,y,0,j))l=z.substring(0,j);}return l;}

Length: 251

Long version

    public static String prefix(String sentence) {
        String[] strings = sentence.split(" ");
        String longest = "";
        for (int a = 0, i = strings.length; a < i; a++) {
            String string1 = strings[a];
            for (int b = a + 1; b < i; b++) {
                String string2 = strings[b];
                int maxLen = Math.max(string1.length(), string2.length());
                for (int j = longest.length(); j < maxLen; j++) {
                    if (string1.regionMatches(true, 0, string2, 0, j)) {
                        longest = string1.substring(0, j);
                    }
                }
            }
        }
        return longest;
    }
7

Functional approach, 380 characters:

import java.util.stream.*;public static String prefix(String q){return f(q.toLowerCase(),1);}static String f(String q, int i) {String p=Stream.of(q.split(" ")).filter(s->s.length()>=i).collect(Collectors.toMap(s->s.substring(0,i),v->1,(l,r)->l+r)).entrySet().stream().filter(e->e.getValue()>1).reduce("",(l,r)->r.getKey(),(l,r)->r);return p.isEmpty()||(q=f(q,i+1)).isEmpty()?p:q;}

Readable format:

import java.util.stream.*;

public static String prefix(String q) {
    return f(q.toLowerCase(), 1);
}

static String f(String q, int i) {
    String p = Stream.of(q.split(" "))
        .filter(s -> s.length() >= i)
        .collect(Collectors.toMap(s -> s.substring(0, i), v -> 1, (l, r) -> l + r))
        .entrySet().stream()
        .filter(e -> e.getValue() > 1)
        .reduce("", (l, r) -> r.getKey(), (l, r) -> r);
    return p.isEmpty() || (q = f(q, i + 1)).isEmpty() ? p : q;
}

Edit: simpler, shorter version:

362 characters.

import java.util.HashMap;public static String prefix(String s){HashMap<String,Integer>c=new HashMap<>();for(String p:s.toLowerCase().split(" "))for(int i=1;i<=p.length();i++)c.merge(p.substring(0,i),1,(l,r)->l+r);return c.entrySet().stream().filter(e->e.getValue()>1).sorted((l,r)->l.getKey().length()-r.getKey().length()).reduce("",(l,r)->r.getKey(),(l,r)->r);}

public static String prefix(String s) {
    HashMap<String, Integer> c = new HashMap<>();
    for (String p : s.toLowerCase().split(" "))
        for (int i = 1; i <= p.length(); i++)
            c.merge(p.substring(0, i), 1, (l, r) -> l + r);
    return c.entrySet().stream()
        .filter(e -> e.getValue() > 1)
        .sorted((l, r) -> l.getKey().length() - r.getKey().length())
        .reduce("", (l, r) -> r.getKey(), (l, r) -> r);
}
8

Short:

public static String longestPrefix(String sentence) {
    String[] words = sentence.split(" ");
    String longestPrefix = "";

    for (int i = 0; i < words.length - 1; i++) {
        for (int j = i + 1; j < words.length; j++) {
            for (int k = words[i].length(); k > 0; k--) {
                String s = words[i].substring(0, k).toLowerCase();

                if (words[j].toLowerCase().indexOf(s) == 0
                        && s.length() > longestPrefix.length())
                    longestPrefix = s;
            }
        }
    }

    return longestPrefix;
}

Shorter:

public static String p(String a) {
    String[] b = a.split(" ");
    a = "";
    String s;

    for (int i = 0, j, k, l = b.length; i < l; i++)
        for (j = i; ++j < l;)
            for (k = a.length(); k <= b[i].length();)
                a = b[j].toLowerCase().indexOf(
                        s = b[i].substring(0, k++).toLowerCase()) == 0 ? s : a;

    return a;
}

Shortest; 240 characters:

public static String p(String a){String[]b=a.split(" ");a="";String s;for(int i=0,j,k,l=b.length;i<l;i++)for(j=i;++j<l;)for(k=a.length();k<=b[i].length();)a=b[j].toLowerCase().indexOf(s=b[i].substring(0,k++).toLowerCase())==0?s:a;return a;}
9

170 Characters

public static String p(String s){String b="";for(Matcher m=Pattern.compile("(\\b\\w*)(?=.*\\1)",2).matcher(s);m.find();b=s.length()>b.length()?s:b)s=m.group();return b;}

Unminified:

public static String p(String s) {
    String b = "";
    for (Matcher m = Pattern.compile("(\\b\\w*)(?=.* \\1)", 2).matcher(s);
            m.find();
            b = s.length() > b.length() ? s : b)
        s = m.group();
    return b;
}

Replace the back tick with \1, because the forum is replacing it and I can’t figure out how to prevent it.

1 Like
10

@jus1in I can’t seem to get your solution to work.

Edit: Found why; you need to change $1 to \1 (and escape the \)

11

Edited. I had thought dollar sign back-references in the matching string worked, but I guess I accidentally tested a different version of my program. For some reason the forum is replacing double backslash 1 with \\1, and I can’t figure out how to prevent that

1 Like
12

Congratulations to @jus1in once again for winning the weekly programming contest! The next challenge will be up shortly.