In this lab we look at the solution to the Kangaroo
labtest problem.
The problem statement is here.
It is often useful to sketch out a solution using plain English before attempting to write code. To make it easier to translate your solution to Java you can use Java-like structures such as loops in your sketch, but generally you leave out the details.
The first step of the solution is to create a loop that accepts input until the user enters Ctrl-D.
ask for input
while there is still input
No input validation is required and the problem statement says that you can assume the words are entered in lower case. The next step is to read in the two words:
ask for input
while there is still input
read the first word
read the second word
Now you need to solve the kangaroo problem: are the letters of the second word contained in the first word in order? If you ignore the in order part, the problem becomes simpler: are the letters of the second word contained in the first word? You can solve this problem by taking each character of the second word one character at a time and checking if the character is in the first word:
ask for input
while there is still input
read the first word
read the second word
for each character in the second word
find the index of the character in the first word
if the index is not -1
first word might be kangaroo word
else
first word is not a kangaroo word
If the first word might be a kangaroo word, you need to store the index of the found character; next time through the loop, you will start looking for the next character after the stored index. This solves the "in order" part of the problem:
ask for input while there is still input read the first word read the second word prevIndex = -1 for each character in the second word find the index of the character in the first word starting at prevIndex + 1 if the index is not -1 first word might be kangaroo word prevIndex = index else first word is not a kangaroo word
You want the loop to stop running if the first word is not a kangaroo word. You can do this by creating a boolean variable that is true if the first word might be a kangaroo word. If the variable ever becomes false, you can terminate the loop.
ask for input while there is still input read the first word read the second word isKangaroo = true prevIndex = -1 for each character in the second word and isKangaroo is true find the index of the character in the first word starting at prevIndex if the index is not -1 first word might be kangaroo word prevIndex = index else first word is not a kangaroo word isKangaroo = false
Now you can deal with the issue of making the found characters in the first word uppercase. Recall that you cannot modify the contents of a string, but you can modify the contents of a string buffer. All you have to do is put a copy of the first word into a string buffer and capitalize letters in the string buffer whenever a character is found in the first word:
ask for input while there is still input read the first word read the second word buffer = first word isKangaroo = true prevIndex = -1 for each character in the second word and isKangaroo is true find the index of the character in the first word starting at prevIndex if the index is not -1 first word might be kangaroo word capitalize letter at index in buffer prevIndex = index else first word is not a kangaroo word isKangaroo = false
Finally, your program should output the result and ask for the next input:
ask for input
while there is still input
read the first word
read the second word
buffer = first word
isKangaroo = true
prevIndex = -1
for each character in the second word and isKangaroo is true
find the index of the character in the first word starting at prevIndex
if the index is not -1
first word might be kangaroo word
capitalize letter at index in buffer
prevIndex = index
else
first word is not a kangaroo word
isKangaroo = false
if isKangaroo
output the buffer
else
output "not a kangaroo word"
ask for input
ask for input
while there is still input
read the first word
read the second word
buffer = first word
isKangaroo = true
prevIndex = -1
for each character in the second word and isKangaroo is true
find the index of the character in the first word starting at prevIndex
if the index is not -1
first word might be kangaroo word
capitalize letter at index in buffer
prevIndex = index
else
first word is not a kangaroo word
isKangaroo = false
if isKangaroo
output the buffer
else
output "not a kangaroo word"
ask for input
import java.io.PrintStream;
import java.util.Scanner;
public class Kangaroo
{
public static void main(String[] args)
{
PrintStream output = System.out;
Scanner input = new Scanner(System.in);
output.print("Enter two words, or Ctrl-d to quit: ");
for (; input.hasNext(); )
{
}
}
}
ask for input
while there is still input
read the first word
read the second word
buffer = first word
isKangaroo = true
prevIndex = -1
for each character in the second word and isKangaroo is true
find the index of the character in the first word starting at prevIndex
if the index is not -1
first word might be kangaroo word
capitalize letter at index in buffer
prevIndex = index
else
first word is not a kangaroo word
isKangaroo = false
if isKangaroo
output the buffer
else
output "not a kangaroo word"
ask for input
import java.io.PrintStream;
import java.util.Scanner;
public class Kangaroo
{
public static void main(String[] args)
{
PrintStream output = System.out;
Scanner input = new Scanner(System.in);
output.print("Enter two words, or Ctrl-d to quit: ");
for (; input.hasNext(); )
{
String first = input.next();
String second = input.next();
StringBuffer buffer = new StringBuffer(first);
boolean isKangaroo = true;
int prevIndex = -1;
}
}
}
ask for input
while there is still input
read the first word
read the second word
buffer = first word
isKangaroo = true
prevIndex = -1
for each character in the second word and isKangaroo is true
find the index of the character in the first word starting at prevIndex
if the index is not -1
first word might be kangaroo word
capitalize letter at index in buffer
prevIndex = index
else
first word is not a kangaroo word
isKangaroo = false
if isKangaroo
output the buffer
else
output "not a kangaroo word"
ask for input
import java.io.PrintStream;
import java.util.Scanner;
public class Kangaroo
{
public static void main(String[] args)
{
PrintStream output = System.out;
Scanner input = new Scanner(System.in);
output.print("Enter two words, or Ctrl-d to quit: ");
for (; input.hasNext(); )
{
String first = input.next();
String second = input.next();
StringBuffer buffer = new StringBuffer(first);
boolean isKangaroo = true;
int prevIndex = -1;
for (int i = 0; i < second.length() && isKangaroo; i++)
{
char c = second.charAt(i);
int index = first.indexOf(c, prevIndex + 1);
if (index != -1)
{
buffer.setCharAt(index, Character.toUpperCase(c));
prevIndex = index;
}
else
{
isKangaroo = false;
}
}
}
}
}
ask for input
while there is still input
read the first word
read the second word
buffer = first word
isKangaroo = true
prevIndex = -1
for each character in the second word and isKangaroo is true
find the index of the character in the first word starting at prevIndex
if the index is not -1
first word might be kangaroo word
capitalize letter at index in buffer
prevIndex = index
else
first word is not a kangaroo word
isKangaroo = false
if isKangaroo
output the buffer
else
output "not a kangaroo word"
ask for input
import java.io.PrintStream;
import java.util.Scanner;
public class Kangaroo
{
public static void main(String[] args)
{
PrintStream output = System.out;
Scanner input = new Scanner(System.in);
output.print("Enter two words, or Ctrl-d to quit: ");
for (; input.hasNext(); )
{
String first = input.next();
String second = input.next();
StringBuffer buffer = new StringBuffer(first);
boolean isKangaroo = true;
int prevIndex = -1;
for (int i = 0; i < second.length() && isKangaroo; i++)
{
char c = second.charAt(i);
int index = first.indexOf(c, prevIndex + 1);
if (index != -1)
{
buffer.setCharAt(index, Character.toUpperCase(c));
prevIndex = index;
}
else
{
isKangaroo = false;
}
}
if (isKangaroo)
{
output.printf("%s is a kangaroo word%n%n", buffer, second);
}
else
{
output.println("not a kangaroo word\n");
}
output.print("Enter two words, or Ctrl-d to quit: ");
}
}
}