首页 > 其他 > 详细

Leetcode: Find And Replace in String

时间:2019-10-18 13:42:54      阅读:59      评论:0      收藏:0      [点我收藏+]
To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y.  The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y.  If not, we do nothing.

For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".

Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = ‘c‘, which doesn‘t match x[0] = ‘e‘.

All these operations occur simultaneously.  It‘s guaranteed that there won‘t be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.

Example 1:

Input: S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
Output: "eeebffff"
Explanation: "a" starts at index 0 in S, so it‘s replaced by "eee".
"cd" starts at index 2 in S, so it‘s replaced by "ffff".
Example 2:

Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation: "ab" starts at index 0 in S, so it‘s replaced by "eee". 
"ec" doesn‘t starts at index 2 in the original S, so we do nothing.
Notes:

0 <= indexes.length = sources.length = targets.length <= 100
0 < indexes[i] < S.length <= 1000
All characters in given inputs are lowercase letters.

HashMap

 1 class Solution {
 2     public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
 3         StringBuilder res = new StringBuilder();
 4 
 5         HashMap<Integer, Integer> map = new HashMap<>();
 6         for (int i = 0; i < indexes.length; i ++) {
 7             map.put(indexes[i], i);
 8         }
 9         
10         for (int i = 0, matchLen = 0; i < S.length(); i += matchLen) {
11             matchLen = 1;
12             
13             if (map.containsKey(i)) {
14                 int p = map.get(i); // p is the index in indexes[]
15                 if (S.startsWith(sources[p], i)) {
16                     res.append(targets[p]);
17                     matchLen = sources[p].length();
18                 }
19                 else res.append(S.charAt(i));
20             }
21             else res.append(S.charAt(i));
22         }
23         return res.toString();
24     }
25 }

 

Sort and replace S from right to left (未深究)

 1     public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
 2         List<int[]> sorted = new ArrayList<>();
 3         for (int i = 0 ; i < indexes.length; i++) sorted.add(new int[]{indexes[i], i});
 4         Collections.sort(sorted, Comparator.comparing(i -> -i[0]));
 5         for (int[] ind: sorted) {
 6             int i = ind[0], j = ind[1];
 7             String s = sources[j], t = targets[j];
 8             if (S.substring(i, i + s.length()).equals(s)) S = S.substring(0, i) + t + S.substring(i + s.length());
 9         }
10         return S;
11     }

 

Leetcode: Find And Replace in String

原文:https://www.cnblogs.com/EdwardLiu/p/11697731.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!