0ms C++ code


  • 0
    C

    We can solve the problem by the follwing way:
    consider input "234"
    a a a a a a a a a b b b b b b b b b c c c c c c c c c
    d d d e e e f f f|d d d e e e f f f |d d d e e e f f f
    g h i |g h i| g h i| g h i| g h i | g h i| g h i| g h i| g h i
    line 1:period times=1,period length=27,because '2' refers to 3 charaters,so it cut every peried into 3 part.
    line 2:period times=3,period length=9,because '3' refers to 3 charaters,so it cut every peried into 3 part.
    line 3:period times=9,period length=3,because '4' refers to 3 charaters,so it cut every peried into 3 part.
    And here is my 0ms runtime code:

    vector<string> letterCombinations(string digits) {
    		vector<string> s;
    		if(digits.empty()) return s;
    		int size = 1;
    		char table[8][4] = {
    			{ 'a', 'b', 'c' }, { 'd', 'e', 'f' },
    			{ 'g', 'h', 'i' }, { 'j', 'k', 'l' }, { 'm', 'n', 'o' },
    			{ 'p', 'q', 'r', 's' }, { 't', 'u', 'v' }, { 'w', 'x', 'y', 'z' }
    		};
    		//check if there is '1' or '0'
    		int N = digits.size();
    		for (int i = 0; i<N; ++i){
    			if (digits[i] >= '2'&&digits[i] <= '9'){
    				if (digits[i] == '7' || digits[i] == '9')
    					size = size * 4;
    				else
    					size = size * 3;
    			}
    			else
    				return s;//illegal input, return an empty vector
    		}
    		s.resize(size);
    		int mod;
    		int length=size;
    		int times = size / length;
    		for (int i = 0; i < N; ++i){
    			if (digits[i] == '7' || digits[i] == '9')
    				mod = 4;
    			else
    				mod = 3;
    			for (int j = 0; j < times;++j)
    				for (int k = 0; k < length; ++k){
    					s[j*length + k].push_back(table[digits[i] - '2'][k / (length / mod)]);
    				}
    			times = times*mod;
    			length = length / mod;
    		}
    		return s;
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.