Certain letters of the alphabet are “lucky”. The first “lucky” letter of the alphabet is “a”, and every 2nd letter after a is also considered “lucky”. In this way lucky letters include “a”, “c”, “e”, “g” … etc. The alphabet consists of the lowercase letters a-z.
A word is considered “lucky” if it contains at least 4 “lucky” characters e.g. “asks”. Given an Array of N Strings (where each string contains a sentence) write a class which can print out the 2 “luckiest” sentences where “luck” is measured by the number of “lucky” words in the sentence. The goal is to write the most efficient algorithm, optimizing for both space and time. Briefly discuss the computational complexity of your solution.
Example:
Input {“once upon a midnight dreary”, “say aaaaah for the dentist”, “lima is in peru”, “three blind mice see how they run”}
Output:
once upon a midnight dreary
say aaaaah for the dentist
public class Main {
public int countLuck(String s) {
char[] a = s.toCharArray();
int luck = 0;
int count = 0;
for (int i = 0; i < a.length; ++i) {
if (a[i] == ' ') {
if (count >= 4)
++luck;
count = 0;
}
else if (((int)(a[i] - 'a')) % 2 == 0)
++count;
}
return luck;
}
public void luckiest(String[] a) {
int[] c = new int[a.length];
int max1 = -1;
for (int i = 0; i < a.length; ++i) {
c[i] = countLuck(a[i]);
if (max1 < 0)
max1 = i;
else if (c[i] > c[max1])
max1 = i;
}
System.out.println(a[max1]);
int max2 = -1;
for (int i = 0; i < a.length; ++i) {
if (i == max1)
continue;
if (max2 < 0)
max2 = i;
else if (c[i] > c[max2])
max2 = i;
}
System.out.println(a[max2]);
}
public static void main(String[] args) {
Main obj = new Main();
String[] arr = {"once upon a midnight dreary", "say aaaaah for the dentist", "lima is in peru", "three blind mice see how they run"};
obj.luckiest(arr);
}
}
tijoforyou’s solution is incorrect in the countLuck method. There is a bug there. When he uses a[ i ] == ’ ’ to determine if a word has finished, he leaves out the last word of every String because there is no white space after the last word.
To prove my point about tijoforyou’s solution as incorrect, it does not work for the test case: “aaaa aaaa aaaa bbbb”, “aaaa aaaa aaaa aaaa”, “aaaa aaaa aaaa aaac”. The first String has 3 lucky words whereas the last two have 4 each. The correct output should be, therefore, the last two Strings. However, after running this on my computer, tijoforyou’s solution outputs the first two Strings instead. This is because it does not consider the last word of each sentence.
My countLuck method would be like this:
public int countLuck( String s ) {
int luck = 0;
StringTokenizer tokens = new StringTokenizer( s );
while( tokens.hasMoreTokens() ) {
String temp = tokens.nextToken();
int count = 0;
for( int i = 0; i < temp.length(); i++ ) {
if( (int)( temp.charAt( i ) - 'a' ) % 2 == 0 )
count++;
}
if( count >= 4 )
luck++;
}
return luck;
}
even it is not necessary just check the character by character and if character is a letter then calculate whether it is lucky number or not otherwise go on next character if its ’ ’
To prove my point about this solution being incorrect, try this with the test case: “aaaa aaaa aaaa bbbb”, “aaaa aaaa aaaa aaaa”, “aaaa aaaa aaaa aaac”. The first String only has 3 lucky words whereas the last two strings both have 4. Therefore, the correct output should be the 2nd and the 3rd String. However, after running this on my computer, it outputs the first and the second String because it does not consider the last word of the whole sentence.
What about the your solution’s complexities?
What would you use to test this code?
What is the string tokenizer actually doing under the hood?
How can you do this with fewer instruction? At least try to impress…
You need to used the Functions and then used the string. Your string are not automatically called by parameters. Its only possible when function called itself.