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

English Version

题目描述

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

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

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

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

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

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

 

示例 1：

示例 2：

 

提示：

• 1 <= s.length <= 105
• 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}$ 的长度。

Python3

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]

Java

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 ' ';
    }
}

C++

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 ' ';
    }
};

Go

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 ' '
}

TypeScript

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 ' ';
}