carloscn
commented
1 year ago Analysis
先写一个简单的字符映射宏定义
#define N2A_MAP(_num) ((char)((_num) + 'A' - 1))
#define A2N_MAP(_char) ((int32_t)((_char) - 'A' + 1))然后开始对字符串进行分割，找组合规律。从插入空格角度考虑，2个字符的话就插入0..1个空格，3个字符就插入0..2个空格，4个字符就插入0..4个空格，因此n个字符就插入 0..n-1个空格。for的外层循环确定。for (i = 0; i < n; i ++)
然后我们以二进制的方式来代表插入的空格，每个字符 0代表没有空格 1代表有空格，然后判断空格就好了。
例如： 字符串长度为3，就2个空格 10 / 01 / 11；字符串长度为4，就3个空格 100 / 010 / 001 / 110 / 101 / 011 / 111； 数字上的规律，就是0 - 2^n - 1。
我们需要单元：数字坐标转字符串（100B -> 1 234），还能判定出是否符合规则，(str, num, len, result)
static bool convert(char *str, int32_t num)
{
bool ret = false;
char *str_rom = NULL;
if (NULL == str) {
goto finish;
}
size_t len = strlen(str) - 1;
str_rom = (char*) calloc(1, 2 * strlen(str) + 1);
if (NULL == str_rom) {
goto finish;
}
size_t i = 0, j = 0, last_pos = 0;
for (i = 0; i < strlen(str); i ++) {
str_rom[j ++] = str[i];
if ((num >> (len - i - 1)) & 0x1 == 1) {
str_rom[j] = '\0';
if (atoi(str_rom + last_pos) > 26) {
goto finish;
}
str_rom[j++] = ' ';
last_pos = j;
}
}
if (atoi(str_rom + last_pos) > 26) {
goto finish;
}
ret = true;
finish:
UTILS_SAFE_FREE(str_rom);
return ret;
}
int32_t num_decode(char *s)
{
int32_t ret = 0;
size_t len = 0;
UTILS_CHECK_PTR(s);
UTILS_CHECK_LEN(len = strlen(s));
while (*s == '0') {
s ++;
}
len = strlen(s);
int32_t i = 0;
for (i = 0; i < pow(2, len - 1); i ++) {
ret += (int32_t) convert(s, i);
}
finish:
return ret;
}
Description
A message containing letters from A-Z can be encoded into numbers using the following mapping:
'A' -> "1" 'B' -> "2" ... 'Z' -> "26" To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:
"AAJF" with the grouping (1 1 10 6) "KJF" with the grouping (11 10 6) Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".
Given a string s containing only digits, return the number of ways to decode it.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1:
Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226" Output: 3 Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "06" Output: 0 Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
Constraints:
1 <= s.length <= 100 s contains only digits and may contain leading zero(s).