Interview#1 Encode&Decode (Facebook)

Writer: Steven, Lee

Date: 12/17, Monday

Purpose: Solving #1 Encode&Decode

Level: Easy

From: Facebook

한국어 버전은 밑에 있습니다.

Caution1: Before you read the solution that I used, you need to solve this problem by yourself

Description: Given the mapping a = 1, b = 2, ... z = 26, and an encoded message. Count the number of ways it can be decoded. For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'. 

* You can assume that the messages are decodable. For example, '001' is not allowed. *

What is the Idea?

 We need to think of this case into two small cases separated by one or separated by two. For example, '3712251' should be '3', '7', '1', '2', '2', '5', '1' in one case. or '12', '22', '25' in two case. we have to avoid n > 26 case Let's count the number of ways.

int n = 0

1. the case consisted of only one like this '3', '7', '1', '2', '2', '5', '1' => n == 1

2. the case consisted of one and two like this

    '3', '7', '12', '25', '1' => n == 2C1 + 2C2

    '3', '7', '1', '22', '5', '1' => n == 1C1

**** '3', '7', '12', '22', '25', '1' **** <= we are not able to handle this encode massgae like this way. 

2-1. the number of ways it can be decoded in two cases is the number of combinations. 

For example, '3', '7', '12', '25', '1' should be 2C1, 2C2 and '3', '7', '1', '22', '5', '1' should be 1C1

so 2C1 == 2 and 2C2 == 1, 1C1 == 1. 

3. the number of ways is 1 + 2C1 + 2C2 + 1C1 == 5

You need to programming in O(n) at least :)

Check
you can check out your answer in writing comments below.

주의1: 솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.

지문:  a = 1, b = 2, ... z = 26로 되어 있는 맵핑과 인코딩 된 메세지가 주어집니다. 디코딩이 될 수 있는 방법을 다 찾으세요 :) 예로 들어보면 메세지가 '111'로 들어왔다고 하면 3이 됩니다. 왜냐하면 이것은 'aaa', 'ka' 그리고 'ak'가 되기 때문이죠.

* 메세지는 무조건 디코딩이 가능하게 주어집니다. 예를 들어 '001'이라는 메세지는 주어지지 않습니다

아이디어

 우리는 이 주어진 문제들을 두 가지로 크게 분류해야 합니다. 첫 번째는 하나씩 나누는 것과 두 번째는 두개씩 나누는 것입니다. 예를 들어 만약 '3712251'이 들어온다면 '3', '7', '1', '2', '2', '5', '1' 또는 '12', '22', '25' 이 되겠네요. n > 26 경우는 피해야 합니다. 같이 방법의 수를 세봅시다.

1. 오직 한 개의 나누는 것으로 구성된 경우 '3', '7', '1', '2', '2', '5', '1' => n == 1

2. 한 가지와 두가지 경우 모두 합쳐서 구성된 경우

    '3', '7', '12', '25', '1' => n == 2C1 + 2C2

    '3', '7', '1', '22', '5', '1' => n == 1C1

**** '3', '7', '12', '22', '25', '1' **** <= 인코딩 메세지를 이런식으로는 할 수가 없습니다.

2-1. 두 가지 경우 안에서 디코딩 되는 것은 조합의 수입니다. 예를 들어, '3', '7', '12', '25', '1' 은 2C1,  2C2 그리고 

3', '7', '1', '22', '5', '1'은 1C1 따라서 2C1 == 2 그리고 2C2 == 1, 1C1 == 1입니다.

3. 따라서 이 예시의 경우의 수는 n = 1 + 2 + 1 + 1 == 5 입니다.

정답

아래의 코멘트 창에 본인이 만든 코드를 올려주시면 정답확인을 해드리겠습니다. :)

Code & 코드

You need to read the code by yourself

스스로 코드를 읽을 줄 알아야 합니다.

public class DecodeNEncode {
	public static int countingDecode(String encodedMessage) {
		if(encodedMessage.length() < 2) return 1;
		
		int aTwoCombiCnt = 1, bTwoCombiCnt = 1, n1 = 0, n2 = 0, result = 1;
		String[] decodeArr = encodedMessage.split(""); 
		int lenDec = decodeArr.length;
		for(int i = 0 ; i < lenDec; i+=2) {		
			if(i+1 < lenDec && Integer.parseInt(decodeArr[i]) <= 2 && Integer.parseInt(decodeArr[i+1]) <= 6) {
				n1++; 
				aTwoCombiCnt *= n1;
			}
			if(i+2 < lenDec && Integer.parseInt(decodeArr[i+1]) <= 2 && Integer.parseInt(decodeArr[i+2]) <= 6) {
				n2++; 
				bTwoCombiCnt *= n2;
			}
		}
		int n = n1 > n2 ? n1 : n2;
		for(int i = 1 ; i <= n ; i++) {
			if(i <= n1) result += (aTwoCombiCnt / i);
			if(i <= n2) result += (bTwoCombiCnt / i);
		}
		return result;
	}
	public static void main(String[] args) {
		int result = countingDecode("3712251");
		System.out.println(result);
	}
}