当前位置: 面试刷题>> 解码方式 (经典算法题500道)


首先,由于题目描述不完全,我将假设一个常见的“解码方式”题目场景,即给定一个只包含数字和字母'a-z'的字符串,其中每个非零数字d后面可能跟着最多两个小写字母,这种格式表示d个连续的小写字母序列,按字母顺序排列。例如,"3[a]2[bc]" 应该解码为 "aaabcbc"。然而,这里我们简化为只考虑数字后面紧跟一个或多个字母(不显式使用[]),且直接解码,不考虑复杂的嵌套或特殊字符。

题目描述(补充)

给定一个只包含数字和小写字母的字符串 s,其中数字表示后面跟随的字母需要重复的次数。请编写一个函数来解码这个字符串。

示例

输入: "3a2b" 输出: "aaabbb"

输入: "3[a]2[bc]"
注意:此输入格式超出简化场景,但为完整性提及。实际处理中应忽略[],或假定输入格式如上述简化。

PHP 示例代码

function decodeString($s) {
    $stack = [];
    $currString = '';
    $currNum = 0;

    for ($i = 0; $i < strlen($s); $i++) {
        $char = $s[$i];

        if (is_numeric($char)) {
            $currNum = $currNum * 10 + intval($char);
        } elseif ($char === '[') {
            $stack[] = [$currString, $currNum];
            $currString = '';
            $currNum = 0;
        } elseif ($char === ']') {
            $prevString = $stack[array_key_last($stack)][0];
            $prevNum = $stack[array_key_last($stack)][1];
            array_pop($stack);
            $currString = str_repeat($currString, $prevNum) . $prevString;
        } else {
            $currString .= $char;
        }
    }

    return str_repeat($currString, $currNum);
}

// 简化场景下的处理(不考虑[])
function decodeStringSimplified($s) {
    $stack = [];
    $currString = '';
    $currNum = 0;

    for ($i = 0; $i < strlen($s); $i++) {
        $char = $s[$i];

        if (is_numeric($char)) {
            $currNum = $currNum * 10 + intval($char);
            if ($i + 1 < strlen($s) && !is_numeric($s[$i + 1])) {
                $currString .= str_repeat($s[$i + 1], $currNum);
                $i++;
                $currNum = 0;
            }
        } else {
            $currString .= $char;
        }
    }

    return $currString;
}

echo decodeStringSimplified("3a2b"); // 输出: aaabbb

注意:上述decodeString函数考虑了[]的情况,但根据题目简化的要求,应使用decodeStringSimplified函数。

Python 示例代码

def decodeStringSimplified(s):
    stack = []
    num = 0
    curr_str = ""

    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)
        elif char.isalpha():
            if num:
                stack.append(curr_str)
                curr_str = char * num
                num = 0
            else:
                curr_str += char

    return curr_str + ''.join(stack[::-1]) if stack else curr_str

print(decodeStringSimplified("3a2b"))  # 输出: aaabbb

JavaScript 示例代码

function decodeStringSimplified(s) {
    let stack = [];
    let num = 0;
    let currStr = '';

    for (let char of s) {
        if (!isNaN(char)) {
            num = num * 10 + parseInt(char);
        } else if (char === '[') {
            stack.push([currStr, num]);
            currStr = '';
            num = 0;
        } else if (char === ']') {
            // 简化场景下不处理']',因为假设没有嵌套
            throw new Error('Unexpected "]" character');
        } else {
            if (num > 0) {
                currStr = char.repeat(num) + currStr;
                num = 0;
            } else {
                currStr += char;
            }
        }
    }

    return currStr;
}

console.log(decodeStringSimplified("3a2b")); // 输出: aaabbb

请注意,JavaScript 示例中省略了对']'的处理,因为它在简化场景中不适用。如果输入包含[],则需要更复杂的逻辑来正确处理嵌套。

推荐面试题