FindAndReplaceInString [source code]
public class FindAndReplaceInString {
static
/****************************************************************************/
class Solution {
public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
int N = S.length ();
StringBuilder sb = new StringBuilder ();
Map<Integer, Integer> lookup = new HashMap<> ();
for (int i = 0; i < indexes.length; i++) {
lookup.put (indexes[i], i);
}
Arrays.sort (indexes);
int i = 0, index_seed = 0;
while (i < N) {
while (i < indexes[index_seed] && i < N) {
sb.append (S.charAt (i++));
}
if (i < N) {
if (S.substring (i).startsWith (sources[lookup.get (indexes[index_seed])])) {
sb.append (targets[lookup.get (indexes[index_seed])]);
i += sources[lookup.get (indexes[index_seed])].length ();
} else {
sb.append (S.charAt (i++));
}
index_seed++;
}
if (index_seed == indexes.length) {
while (i < N)
sb.append (S.charAt (i++));
break;
}
}
return sb.toString ();
}
}
/****************************************************************************/
public static void main(String[] args) {
FindAndReplaceInString.Solution tester = new FindAndReplaceInString.Solution();
String[][] inputs = {
{"abcd"}, {"a","cd"}, {"eee","ffff"}, {"eeebffff"},
{"abcd"}, {"ab","ec"}, {"eee","ffff"}, {"eeecd"},
{"rozuwxuzmn"}, {"oz","uw","uz"}, {"r","nm","xcw"}, {"rrnmxxcwmn"},
{"vmokgggqzp"}, {"kg","ggq","mo"}, {"s","so","bfr"}, {"vbfrssozp"},
{"jjievdtjfb"}, {"md","tjgb","jf"}, {"foe","oov","e"}, {"jjievdtjfb"},
};
int[][] indices = {
{0, 2},
{0, 2},
{1, 3, 6},
{3, 5, 1},
{4,6,1},
};
for (int i = 0; i < inputs.length / 4; i++) {
System.out.println (Printer.separator ());
String S = inputs[4 * i][0], ans = inputs[4 * i + 3][0];
String[] sources = inputs[4 * i + 1], targets = inputs[4 * i + 2];
int[] indexes = indices[i];
String indexes_str = Printer.array (indices[i]);
String output = tester.findReplaceString (S, indexes, sources, targets);
System.out.printf ("%s\n%s\n%s\n%s\n%s\n%s\n",
S, indexes_str, Printer.array (sources), Printer.array (targets), Printer.wrap (output, output.equals (ans) ? 92 : 91), ans
);
}
}
}
所以这题到底考什么? 看起来很简单但是是一个medium, 感觉有坑?
想不通, 先乱写; 好像是一个分段操作?
test4只能用恶心来形容; 简直是脑筋急转弯;
大概意思就是所有给你的这些输入其实并不是默认就是排好序的; 要自己完成这个排序; 当然, 这个其实也可以理解为是一种提示: 这题确实是要排好序之后更好做;
不需要封装
不过封装更简单;
这题好多坑啊, 真的是; 后来发现其实主要还是自己写的太粗心了; 比如无论匹配是否成功, seed都应该++, 这个一开始也没有想好; 总体其实还是不错的一个题目;
考察的地方不在于算法的设计, 而在于这样一个看起来很简单的算法, 你能不能很快很好的实现出来;
UNFINISHED
editorial
Approach #1: Direct [Accepted]
Intuition and Algorithm
We showcase two different approaches. In both approaches, we work on finding whether the replacement operation is successful or not.
In Java, we work with a match array, recording match[ix] = i if the ith replacement operation is successful and involves the index S[ix]. Because the limits are low, we can work with substrings for convenience.
面试的时候能不能这样偷懒就很难说了;
Then, we build the answer using this match array. We repeatedly either write the next character S[ix], or targets[match[ix]] depending on the value of match[ix].
In Python, we sort our replacement jobs (i, x, y) in reverse order. If S[i:].startswith(x) (we use a longer check that checks each index), then we can replace that section S[i:i+len(x)] with the target y. We used a reverse order so that edits to S do not interfere with the rest of the queries.
这个描述的基本就是uwi的那个做法了, 而且这个倒序他那里确实也是用到了的; 这里看出来原因了; 所以这个还是不错的;
那么其实这个用substring的做法本身并不trivial? 或许本来就是面试官希望看到的解法, 并且希望看到你想到这个倒序的操作?
那么怎么知道可以用substring呢? 毕竟这个东西一般来说都是需要尽可能规避的;
can we use substring
或许涉及到这种string操作的, 都可以直接问一下算了; 毕竟substring这个东西是有点特殊, string题目如果允许使用substring, 最后的方便程度会大幅度的提高;
但是用substring最后是很容易带来复杂度的上升的, 这个Trade-Off你要很清楚, 最好还要跟面试官提出来;
class Solution {
public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
int N = S.length();
int[] match = new int[N];
Arrays.fill(match, -1);
for (int i = 0; i < indexes.length; ++i) {
int ix = indexes[i];
if (S.substring(ix, ix + sources[i].length()).equals(sources[i]))
match[ix] = i;
}
StringBuilder ans = new StringBuilder();
int ix = 0;
while (ix < N) {
if (match[ix] >= 0) {
ans.append(targets[match[ix]]);
ix += sources[match[ix]].length();
} else {
ans.append(S.charAt(ix++));
}
}
return ans.toString();
}
}
可以看到, 他这个写法实际上跟我的思路本质上是非常类似的; 那么为什么, 他这个最后会比我这个简单这么多?
dense vs. sparse
实际上, 是因为我写的时候, 还是延用了题目本身的设定, 也就是所有的datum, 最后都是默认用的题目给的这种有点类似sparse的设定;
这样我写的时候就比较麻烦, 比如, 要维护一个seed, 而且循环本身写法也要用eager nested looping来跟seed进行一个匹配;
但是awice这里的写法, 是一个类似于de-sparsify的操作: 他建立了一个s_index -> datum的映射, 但是这个映射并不是只对题目给的这些datum建立, 而是S的所有index, 他都建立, 然后用-1来标记无效位置(没有datum或者datum不match的);
这样一个desparsify的操作之后, 他主循环就好写很多, 直接走一遍就行, 然后用match这个数组里面记录的, 是否有datum的结论, 来完成一个更新操作就行了;
Python写法顺便也贴这:
class Solution(object):
def findReplaceString(self, S, indexes, sources, targets):
S = list(S)
for i, x, y in sorted(zip(indexes, sources, targets), reverse = True):
if all(i+k < len(S) and S[i+k] == x[k] for k in xrange(len(x))):
S[i:i+len(x)] = list(y)
return "".join(S)
因为有zip和sorted, 所以根本不用借助于封装, 最后的代码是很简洁的; 就有点类似uwi的写法;
他说是两个approach, 其实是写在一个approach里面的, 分别放在java版本和Python版本里面;
有人提出:
sasha24 0 a day ago
Java solution has a shortcoming. It does not detect the overlap use case.
source ="abc" sources ={ "ab" , "bc"} target ={"eee","ffff"}
there is an overlap but the implementation returns eeec.
可能也有道理吧, 我没有专门去验证;
虽然说这题, 其实是禁止了有overlap的情况的, 但是真正面试的时候, 能够意识到这种extensibility, 还是有帮助的;
uwi: 8min
class Solution {
class Datum
{
int pos;
String src;
String targ;
}
public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
int m = indexes.length;
Datum[] ds = new Datum[m];
for(int i = 0;i < m;i++){
Datum d = new Datum();
d.pos = indexes[i];
d.src = sources[i];
d.targ = targets[i];
ds[i] = d;
}
Arrays.sort(ds, new Comparator<Datum>() {
public int compare(Datum a, Datum b) {
return a.pos - b.pos;
}
});
for(int i = m-1;i >= 0;i--){
Datum d = ds[i];
if(S.substring(d.pos, d.pos + d.src.length()).equals(d.src)){
S = S.substring(0, d.pos) + d.targ + S.substring(d.pos + d.src.length());
}
}
return S;
}
}
他最后用的是封装的思路来实现一个排序; 还行吧, 都差不多;
不过他主干逻辑比我简单太多了; 这才几行啊;
主循环if header里面的这个判断其实用startsWith更加简单, 不知道为什么他没有用?
他主函数就是用一个现场的直接的substring组合的方式实现的; 按理说其实这样的写法效率不高, 不过他估计又是contest的时候先用慢的写法写写看, 能过就不管;
Problem Description
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.
Difficulty:Medium
Total Accepted:1.1K
Total Submissions:3.3K
Contributor:
awice
Companies
google
Related Topics
string