LeetCode 880. 索引处的解码字符串

Categories:

题目描述
思路分析
1. 解法一：从后往前还原（推荐）
相似题目

题目描述

✅ 880. 索引处的解码字符串

思路分析

解法一：从后往前还原（推荐）

核心思路：

先计算解码后的总长度 size（用 long 防溢出）。

从后向前遍历，遇到数字将 size /= d 并令 k %= size。

遇到字母时，若 k == 0 或 k == size，该字母即答案。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)。

class Solution {
    public String decodeAtIndex(String s, int k) {
        long size = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                size *= ch - '0';
            } else {
                size++;
            }
        }

        long K = k;
        for (int i = s.length() - 1; i >= 0; i--) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                int d = ch - '0';
                size /= d;
                K %= size;
            } else {
                if (K == 0 || K == size) {
                    return String.valueOf(ch);
                }
                size--;
            }
        }

        return "";
    }
}

func decodeAtIndex(s string, k int) string {
	size := int64(0)
	for i := 0; i < len(s); i++ {
		ch := s[i]
		if ch >= '0' && ch <= '9' {
			size *= int64(ch - '0')
		} else {
			size++
		}
	}

	K := int64(k)
	for i := len(s) - 1; i >= 0; i-- {
		ch := s[i]
		if ch >= '0' && ch <= '9' {
			d := int64(ch - '0')
			size /= d
			K %= size
		} else {
			if K == 0 || K == size {
				return string(ch)
			}
			size--
		}
	}

	return ""
}

相似题目

题目	难度	考察点
394. 字符串解码	中等	递归/栈
639. 解码方法 II	困难	DP
91. 解码方法	中等	DP
1410. HTML 实体解析器	中等	字符串处理
1668. 最大重复子字符串	简单	字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/95625148