题目
LeetCode每日一题,参考833. 字符串中的查找与替换,难度分1461。
解题思路
- 排序+模拟:因为替换后会影响字符串下标的改变,先排序后按顺序替换并记录下一个开始的位置即可模拟替换过程。
排序+模拟
class Solution {
public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
//不重叠 直接按顺序替换
int k = indices.length;
//按照ids顺序访问indices就是下表从小到大开始替换
Integer[] ids = new Integer[k];
for(int i = 0; i < k; i++) ids[i] = i;
Arrays.sort(ids,(a,b)->indices[a]-indices[b]);
//按顺序替换
StringBuilder ans = new StringBuilder();
char[] cs = s.toCharArray();
int pre = 0;//上次替换后结束下标
for(int i = 0; i < k; i++) {
int idx = ids[i], j = indices[idx]; //j访问下标
//先把下标j前面不替换的放到结果ans里
if(j > pre) ans.append(s.substring(pre,j));
//判断是否要替换
if(check(cs,sources[idx].toCharArray(),j)) {
ans.append(targets[idx]);
pre = j + sources[idx].length();
}else {
pre = j;
}
}
if(pre < s.length()) ans.append(s.substring(pre));
return ans.toString();
}
boolean check(char[] s, char[] source, int pos){
if(s.length < pos + source.length) return false;
for(int i = 0; i < source.length; i++) {
if(s[pos+i] != source[i]) return false;
}
return true;
}
}
复杂度分析
- 时间复杂度:
O(k+klogk+n)
,k
为尝试替换数组长度,排序klogk
,n
为字符串长度。 - 空间复杂度:
O(k+logk)
,排序数组k
,排序栈空间logk
。
2023.08.15
网友评论