Monday, August 4, 2014

PrefixCode

Problem:

TopCoder Problem Statement - PrefixCode

Overview:

Determine if a given array of Strings constitutes a prefix code.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 151
04: Division: 2
05: Level: 1
06: Points: 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1700
08:  */
09: 
10: public class PrefixCode {
11: 
12:     public String isOne(String[] words) {
13: 
14:         for (int i = 0; i < words.length - 1; i++) {
15:             for (int j = i + 1; j < words.length; j++) {
16: 
17:                 if (words[i].startsWith(words[j])) {
18:                     return ("No, " + j);
19:                 } else if (words[j].startsWith(words[i])) {
20:                     return ("No, " + i);
21:                 }
22:             }
23:         }
24:         return "Yes";
25:     }
26: }
Notes:

The problem statement is a little confusing. If you just read the first and third paragraphs it makes more sense. The second paragraph adds nothing and just diverts your attention away from what you need to do. All that you need to do here is determine if any string in the given array of strings is a prefix of any other string. If a prefix is present, return the least prefix index.

The solution uses two for loops with one nested inside the other. Note that the outer for loop goes from i = 0 to i < length - 1; while the inner loop goes from j= i + 1 to j < length. The outer loop marches along from left to right, while the inner loop bounces from the current outer position to the end - with it's space getting shorter and shorter as i increases. This pattern gets used over and over again. The nice thing about this setup is that j is always > i - there is no overlap.

Then, for each value of i and j, we check to see if j is a prefix of i. Or, failing that, if i is a prefix of j. As soon as a prefix if found, we will have the lowest index, so we can stop immediately and return it.

If we exit the for loops without having returned, then there are no prefixes - this is a valid prefix code, so return "Yes"

No comments:

Post a Comment