17年商湯筆試題

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
using namespace std;
           

/*
* 編碼規則是a-z 對應1-26
* 輸入一個字元串
* 輸出可能的解碼方案
* sample input 12
* sample output 2
* note : a(1)b(2) or l(12)
* explantion: 采用遞歸方法，對目前串的解碼方案，由第一個字母的解碼方式 和後面串
* 總的解碼方案個數決定
* 若第一個字母隻有一種解碼方式，則總的解碼方案書等于除去第一個字元的子串解碼方案
* 若第一個字母有多種解碼方式，則總的解碼方案數等于每種解碼方式後除去第一個字元的子串解碼方案 之和
* 在這個例子中第一個字母最多有兩種解碼方式（由第一個字元代表的數字解碼，或者由前兩個字元代表的數字解碼）
**/

int num_decode_recursive(string str){
	set<int> alpha ={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
	if(str.length() <= 1){
		return 1;
	}
	else{
			int code = 10*(str[0]-'0') + (str[1]-'0');
			if (code == 0) return 0;
			if( alpha.find(code) != alpha.end()){
					if( (str[1] - '0') != 0){
						int num1 = num_decode_recursive(str.substr(1));
						int num2 = num_decode_recursive(str.substr(2));
						if(num1 == 0 || num2 == 0)
							return 0;
						else
							return num1+num2;
					}
					else
						return num_decode_recursive(str.substr(2));
			}
			else{
				return num_decode_recursive(str.substr(1));
			}

	}
}

/* 非遞歸實作方式*/

int num_decode(string str){
	//num[i] 表示str[0]--str[i] 可能的解碼方案數
	int num[str.length()] = {1};
	//第一個數字不為0，否則無法解碼，方案數為0 
	if( str.length() < 1 || str[0] == '0')
		return 0;
	for(unsigned int i = 1 ; i < str.length(); ++i){ 
		//多一個數字的情況下編碼方案的變化取決于多的數字與前一位數字組合是否是一個字元編碼
		int code = 10*(str[i-1]-'0') + (str[i]-'0');

		if(str[i] != '0' && str[i-1] != '0' && code < 27)
			num[i] = num[i-1]+num[i-2];
		// 前一位是0或者該位是0 或者兩位組成的數大于26
		// 都不能組成新的編碼，則方案數等于str[0]--str[i-1]
		// 的解碼方案數
		else if(str[i] == '0' && str[i-1] == '0')// 連續兩位為0 ，出錯，無法解碼
			return 0;
		else
			num[i] = num[i-1];
	}
	return num[str.length()-1];
}
int main(){
	//cout<<num_decode("31717126241541717")<<endl;
	//cout<<num_decode_recursive("31717126241541717")<<endl;
	//cout<<num_decode("1003");
	//cout<<num_decode_recursive("1003");
           

}