TCHS-3-450

Problem Statement

Three kids are playing the following game: A word is written on a sheet of paper, and one after another, the players take turns adding letters to the word. During each turn, a player must add a single letter to either the beginning or the end of the word. If a player cannot add a letter during his turn, the game ends and that player is declared the loser.

During the game, a player might cheat by making an illegal move. Any move where the player does not add exactly one letter to either the beginning or the end of the word is considered illegal. The only exception is the last move of the game, when the loser adds no letters to the word. Given the log of the game, you must determine whether any of the players cheated.

You are also given the String[]s first, second, and third, containing the chronological lists of words seen by each of the players at the beginning of their turns. Element 0 of first is therefore the original word, element 0 of second is the word after the first player makes his first move, element 0 of third is the word after the second player makes his first move, etc. Return 1, 2, or 3 if the first, second, or third player, respectively, cheated. If multiple players cheated, return the player who cheated first. If nobody cheated, return -1.

Definition

Class:	KidsWordGame
Method:	getCheater
Parameters:	String[], String[], String[]
Returns:	int
Method signature:	int getCheater(String[] first, String[] second, String[] third)
(be sure your method is public)

Constraints

-

first will contain between 1 and 50 elements, inclusive.

-

second and third each will contain between 0 and 50 elements, inclusive.

-

Each element of first, second and third will contain between 0 and 50 characters, inclusive.

-

Each element of first, second and third will contain only lowercase letters ('a'-'z').

-

Define a = the number of elements in first, b = the number of elements in second, c = the number of elements in third. One of the following conditions will hold: a = b = c, a = b+1 = c+1, a = b = c+1.

Examples

0)

{"e","ello"}

{"el","hello"}

{"ell","ello"}

Returns: 2

The second player saw "hello" before making his second move, and then, the third player saw "ello" immediately after the second player made his second move. Therefore, the second player cheated on his second move because "hello" -> "ello" is not a legal move.

1)

{"de","coder","topcoder"}

{"der","pcoder","tipcoder"}

{"oder","opcoder","cheatcoder"}

Returns: 1

The first player cheated on his third turn. "topcoder" -> "tipcoder" is an illegal move.

2)

{"world","sworld"}

{"word"}

{"sword"}

Returns: 1

3)

{"","abcd"}

{"a"}

{"ab"}

Returns: 3

In this case, the third player added more than one letter to the word. Note that the initial word may be empty.

4)

{""}

{}

{}

Returns: -1

5)

{""}

{""}

{""}

Returns: 1

The first player did not add a letter, so he is a cheater.

6)

{"e","wyve","vffwyve","puvffwyvef","bpuvffwyveftl", "tbpuvffwyveftlwz","ttbpuvffwyveftlwzcl", "ttbpuvffwyveftlwzcletq","uuttbpuvffwyveftlwzcletqh", "sjuuttbpuvffwyveftlwzcletqhd","vuysjuuttbpuvffwyveftlwzcletqhd", "vjvuysjuuttbpuvffwyveftlwzcletqhdn", "qsvjvuysjuuttbpuvffwyveftlwzcletqhdnn", "hmqsvjvuysjuuttbpuvffwyveftlwzcletqhdnnj", "ophmqsvjvuysjuuttbpuvffwyveftlwzcletqhdnnjm", "ophmqsvjvuysjuuttbpuvffwyveftlwzcletqhdnnjmudk", "jqophmqsvjvuysjuuttbpuvffwyveftlwzcletqhdnnjmudku"}

{"ve","fwyve","uvffwyve","puvffwyveft","bpuvffwyveftlw","ttbpuvffwyveftlwz", "ttbpuvffwyveftlwzcle","ttbpuvffwyveftlwzcletqh","uuttbpuvffwyveftlwzcletqhd", "ysjuuttbpuvffwyveftlwzcletqhd","jvuysjuuttbpuvffwyveftlwzcletqhd", "vjvuysjuuttbpuvffwyveftlwzcletqhdnn","qsvjvuysjuuttbpuvffwyveftlwzcletqhdnnj", "hmqsvjvuysjuuttbpuvffwyveftlwzcletqhdnnjm", "ophmqsvjvuysjuuttbpuvffwyveftlwzcletqhdnnjmu", "ophmqsvjvuysjuuttbpuvffwyveftlwzcletqhdnnjmudku"}

{"yve","ffwyve","uvffwyvef","puvffwyveftl","tbpuvffwyveftlw","ttbpuvffwyveftlwzc", "ttbpuvffwyveftlwzclet","uttbpuvffwyveftlwzcletqh","juuttbpuvffwyveftlwzcletqhd", "uysjuuttbpuvffwyveftlwzcletqhd","vjvuysjuuttbpuvffwyveftlwzcletqhd", "svjvuysjuuttbpuvffwyveftlwzcletqhdnn","mqsvjvuysjuuttbpuvffwyveftlwzcletqhdnnj", "phmqsvjvuysjuuttbpuvffwyveftlwzcletqhdnnjm", "ophmqsvjvuysjuuttbpuvffwyveftlwzcletqhdnnjmud", "qophmqsvjvuysjuuttbpuvffwyveftlwzcletqhdnnjmudku"}

Returns: -1

import java.util.*;

public class KidsWordGame {

	int getCheater(String[] first, String[] second, String[] third) {
		List<String> words = new ArrayList<String>();
		try {
			for (int i = 0; i < first.length; i++) {
				words.add(first[i]);
				words.add(second[i]);
				words.add(third[i]);
			}
		} catch (Exception e) {}
		for (int i = 0; i < words.size() - 1; i++)
			if (!can_reach(words.get(i), words.get(i + 1)))
				return i % 3 + 1;
		return -1;
	}

	private boolean can_reach(String a, String b) {
		if (b.length() - a.length() == 1 && b.indexOf(a) != -1)
			return true;
		return false;
	}

}