替换字符串中的问号使分数最小
难度:
标签:
题目描述
You are given a string s. s[i] is either a lowercase English letter or '?'.
For a string t having length m containing only lowercase English letters, we define the function cost(i) for an index i as the number of characters equal to t[i] that appeared before it, i.e. in the range [0, i - 1].
The value of t is the sum of cost(i) for all indices i.
For example, for the string t = "aab":
cost(0) = 0cost(1) = 1cost(2) = 0- Hence, the value of
"aab"is0 + 1 + 0 = 1.
Your task is to replace all occurrences of '?' in s with any lowercase English letter so that the value of s is minimized.
Return a string denoting the modified string with replaced occurrences of '?'. If there are multiple strings resulting in the minimum value, return the lexicographically smallest one.
Example 1:
Input: s = "???"
Output: "abc"
Explanation: In this example, we can replace the occurrences of '?' to make s equal to "abc".
For "abc", cost(0) = 0, cost(1) = 0, and cost(2) = 0.
The value of "abc" is 0.
Some other modifications of s that have a value of 0 are "cba", "abz", and, "hey".
Among all of them, we choose the lexicographically smallest.
Example 2:
Input: s = "a?a?"
Output: "abac"
Explanation: In this example, the occurrences of '?' can be replaced to make s equal to "abac".
For "abac", cost(0) = 0, cost(1) = 0, cost(2) = 1, and cost(3) = 0.
The value of "abac" is 1.
Constraints:
1 <= s.length <= 105s[i]is either a lowercase English letter or'?'.
代码结果
运行时间: 157 ms, 内存: 18.2 MB
/*
* 思路：
* 1. 使用Java Stream进行处理，替换问号为不与左右相邻字符相同的最小字母。
* 2. 通过使用Stream的特性，进行逐步转换。
*/
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SolutionStream {
public String modifyString(String s) {
char[] arr = s.toCharArray();
return IntStream.range(0, arr.length)
.mapToObj(i -> {
if (arr[i] == '?') {
return (char) IntStream.range('a', 'z' + 1)
.filter(c -> (i > 0 && arr[i - 1] != c) && (i < arr.length - 1 && arr[i + 1] != c))
.findFirst().orElse('a');
}
return arr[i];
})
.map(String::valueOf)
.collect(Collectors.joining());
}
}解释
方法:
时间复杂度:
空间复杂度: