coask 封 mitaas 在 Piebridge 版# Piebridge - 鹊桥
S*C
1 楼
看了一道twitter面经上的题
Delete SubStrings: 给一个String s和一个String t, 返回一共能在s中删除t多少次
。 例如s = aabb, t = ab, return = 2; s = aabcbdc, t = abc, return 1;=
我基本上没太思考，直接给了最直观的答案，用helperfunction1返回s中与t相同的
subString的起始位置start，用helperfunction2删除s.subString(start, t.length),
外层循环终止条件是helperfunction1返回-1或s.length < t.length,
时间复杂度是O(n^2)。应该有更好的办法，懒得想了，发烧刚好，神智还不太清楚。。。
我写的答案对不对？
public class Solution {
public int countDelete(String s, String t) {
if (s == null || t == null || s.length() < t.length()) {
return 0;
}
int[] res = {0};
rec(s, t, res);
return res[0];
}
private void rec(String s, String t, int[] res) {
if (s.length() < t.length()) {
return;
}
int pos = s.indexOf(t);
if (pos < 0) {
return;
}
res[0]++;
String left = pos >= 0 ? s.substring(0, pos) : "";
String right = pos + t.length() < s.length() ? s.substring(pos + t.
length()) : "";
rec(left + right, t, res);
}
public static void main(String args[]) {
test("aa", "a"); //2
test("abb", "ab"); //1
test("aabb", "ab"); //2
test("aabcbdc", "abc"); //1
test("aabcbdcabc", "abc"); //2
test("abba", "ab"); //1
test("abbab", "ab"); //2
test("abbabb", "abb"); //2
}
static void test(String s, String t) {
System.out.println(sol.countDelete(s, t));
}
static Solution sol = new Solution();
}
Delete SubStrings: 给一个String s和一个String t, 返回一共能在s中删除t多少次
。 例如s = aabb, t = ab, return = 2; s = aabcbdc, t = abc, return 1;=
我基本上没太思考，直接给了最直观的答案，用helperfunction1返回s中与t相同的
subString的起始位置start，用helperfunction2删除s.subString(start, t.length),
外层循环终止条件是helperfunction1返回-1或s.length < t.length,
时间复杂度是O(n^2)。应该有更好的办法，懒得想了，发烧刚好，神智还不太清楚。。。
我写的答案对不对？
public class Solution {
public int countDelete(String s, String t) {
if (s == null || t == null || s.length() < t.length()) {
return 0;
}
int[] res = {0};
rec(s, t, res);
return res[0];
}
private void rec(String s, String t, int[] res) {
if (s.length() < t.length()) {
return;
}
int pos = s.indexOf(t);
if (pos < 0) {
return;
}
res[0]++;
String left = pos >= 0 ? s.substring(0, pos) : "";
String right = pos + t.length() < s.length() ? s.substring(pos + t.
length()) : "";
rec(left + right, t, res);
}
public static void main(String args[]) {
test("aa", "a"); //2
test("abb", "ab"); //1
test("aabb", "ab"); //2
test("aabcbdc", "abc"); //1
test("aabcbdcabc", "abc"); //2
test("abba", "ab"); //1
test("abbab", "ab"); //2
test("abbabb", "abb"); //2
}
static void test(String s, String t) {
System.out.println(sol.countDelete(s, t));
}
static Solution sol = new Solution();
}
