3744. 在展开字符串中查找第 K 个字符 🔒

题目描述

给定一个字符串 s，该字符串由一个或多个单词组成，单词之间用单个空格分隔。s 中的每个单词均由小写的英文字母组成。

我们按如下步骤从 s 得到展开字符串 t：

对于 s 中的每个单词，重复一次它的第一个字符，然后重复两次它的第二个字符，以此类推。

例如，如果 s = "hello world"，那么 t = "heelllllllooooo woorrrllllddddd"。

同时给定一个整数 k，表示字符串 t 的一个合法下标。

返回字符串 t 的第 k 个字符。

示例 1：

输入：s = "hello world", k = 0

输出："h"

解释：

t = "heelllllllooooo woorrrllllddddd"。因此，答案是 t[0] = "h"。

示例 2：

输入：s = "hello world", k = 15

输出：" "

解释：

t = "heelllllllooooo woorrrllllddddd"。因此，答案是 t[15] = " "。

提示：

1 <= s.length <= 10⁵
s 只包含小写英文字母和空格 ' '。
s 不包含 任何前导和后缀空格。
s 中的所有单词都由 一个空格 分隔。
0 <= k < t.length。即 k 是 t 的一个合法下标。

解法

方法一：数学 + 模拟

我们首先将字符串 \(\textit{s}\) 按空格拆分成若干单词。对于每个单词 \(\textit{w}\)，我们可以计算出它在展开字符串 \(\textit{t}\) 中所占的长度 \(m=\frac{(1+|\textit{w}|)\cdot |\textit{w}|}{2}\)。

如果 \(k = m\)，说明第 \(k\) 个字符是空格，直接返回空格即可。

如果 \(k > m\)，说明第 \(k\) 个字符不在当前单词的展开部分，我们将 \(k\) 减去当前单词的展开长度 \(m\) 和空格的长度 \(1\)，继续处理下一个单词。

否则，第 \(k\) 个字符在当前单词的展开部分。我们可以通过模拟展开过程来找到第 \(k\) 个字符：

初始化变量 \(\textit{cur} = 0\)，表示当前已经展开的字符数。
遍历单词 \(\textit{w}\) 的每个字符 \(\textit{w}[i]\)：
- 将 \(\textit{cur}\) 增加 \(i + 1\)。
- 如果 \(k < \textit{cur}\)，说明第 \(k\) 个字符就是 \(\textit{w}[i]\)，返回该字符。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是字符串 \(\textit{s}\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def kthCharacter(self, s: str, k: int) -> str:
        for w in s.split():
            m = (1 + len(w)) * len(w) // 2
            if k == m:
                return " "
            if k > m:
                k -= m + 1
            else:
                cur = 0
                for i in range(len(w)):
                    cur += i + 1
                    if k < cur:
                        return w[i]

class Solution {
    public char kthCharacter(String s, long k) {
        for (String w : s.split(" ")) {
            long m = (1L + w.length()) * w.length() / 2;
            if (k == m) {
                return ' ';
            }
            if (k > m) {
                k -= m + 1;
            } else {
                long cur = 0;
                for (int i = 0;; ++i) {
                    cur += i + 1;
                    if (k < cur) {
                        return w.charAt(i);
                    }
                }
            }
        }
        return ' ';
    }
}

class Solution {
public:
    char kthCharacter(string s, long long k) {
        stringstream ss(s);
        string w;
        while (ss >> w) {
            long long m = (1 + (long long) w.size()) * (long long) w.size() / 2;
            if (k == m) {
                return ' ';
            }
            if (k > m) {
                k -= m + 1;
            } else {
                long long cur = 0;
                for (int i = 0;; ++i) {
                    cur += i + 1;
                    if (k < cur) {
                        return w[i];
                    }
                }
            }
        }
        return ' ';
    }
};

func kthCharacter(s string, k int64) byte {
    for _, w := range strings.Split(s, " ") {
        m := (1 + int64(len(w))) * int64(len(w)) / 2
        if k == m {
            return ' '
        }
        if k > m {
            k -= m + 1
        } else {
            var cur int64
            for i := 0; ; i++ {
                cur += int64(i + 1)
                if k < cur {
                    return w[i]
                }
            }
        }
    }
    return ' '
}

function kthCharacter(s: string, k: number): string {
    for (const w of s.split(' ')) {
        const m = ((1 + w.length) * w.length) / 2;
        if (k === m) {
            return ' ';
        }
        if (k > m) {
            k -= m + 1;
        } else {
            let cur = 0;
            for (let i = 0; ; ++i) {
                cur += i + 1;
                if (k < cur) {
                    return w[i];
                }
            }
        }
    }
    return ' ';
}

3744. 在展开字符串中查找第 K 个字符 🔒

题目描述

解法

方法一：数学 + 模拟

评论