Thursday, September 4, 2014

LongWordsDiv2

Problem:

TopCoder Problem Statement - LongWordsDiv2

Overview:

Determine if a string meets a given set of criteria.

Java Source:
01: public class LongWordsDiv2 {
02: 
03:     public String find(String word) {
04:         return (checkWord(word)) ? "Likes" : "Dislikes";
05:     }
06: 
07:     private boolean checkWord(String word) {
08: 
09:         for (int i = 0; i < word.length(); i++) {
10:             // Check for all upper case
11:             if ((word.charAt(i) < 'A') || (word.charAt(i) > 'Z')) {
12:                 return false;
13:             }
14:         }
15: 
16:         // Check for next character matches
17:         for (int i = 0; i < (word.length() - 1); i++) {
18:             if (word.charAt(i) == word.charAt(i + 1)) {
19:                 return false;
20:             }
21:         }
22: 
23:         /*
24:         * Check for pattern xyxy
25:         * */
26:         for (int i = 0; i < word.length() - 1; i++) {
27:             for (int j = i + 1; j < word.length(); j++) {
28:                 String regex = ".*" + word.charAt(i) + ".*" + word.charAt(j)
29:                         + ".*" + word.charAt(i) + ".*" + word.charAt(j) + ".*";
30:                 if (word.matches(regex)) {
31:                     return false;
32:                 }
33:             }
34:         }
35: 
36:         return true;
37:     }
38: }
Notes:

There are three conditions that we need to check:

  1. Each letter must be an uppercase, english letter.
  2. There are no consecutive letters
  3. There are no patters of the form xyxy - where are and why are any (not necessarily distinct) seqquences of characters

The first condition is actually unnecessary since the problem's constraints guarantee that each character will be an uppercase English letter. Nevertheless, I've choosen to include the check. Note that, technically, we can't use Character.isUpperCase() to test the character, since isUpperCase() will return true for some non-English characters. But, again, it's sort of a moot point.

For the second condition, we just loop through each character and look at the next character. Just be careful to stop the loop one character early, so that looking at the next position is not out of bounds.

The last condition is the trickiest, but it's not that hard if you allow regular expressions expressions to do all the work. We build the following regular expression .*x.*y.*x.*x.* and if our word matches that, return false. We do however need two nested for loops in order to check each letter with each possible following letter.

No comments:

Post a Comment