S*******C
发帖数: 822 | 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();
} | S*******C
发帖数: 822 | 2 刚写了一个简化版：
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;
}
String replaced = s.replaceFirst(t, "");
if(replaced.length() < s.length()){
res[0]++;
rec(replaced, t, res);
}
} | t*********r
发帖数: 63 | 3 第一反应是贪心，能删就删，能不就看看下一个字符是不是这个子串的第一个字符，是
就递归找，然后O(N)复杂度。没细想，有可能是错的。 | r*******y
发帖数: 270 | | g******d
发帖数: 152 | 5 s = ABABAA
t = ABA
结果应该是2
贪心删除法，得到 1 | w******g
发帖数: 262 | 6 dp issue
[在 SpringMVC (Tutorial) 的大作中提到：]
：看了一道twitter面经上的题
：
：........... | R*********4
发帖数: 293 | 7 你的编程习惯，在大多数公司里都是要挂的。
比如这个
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];
}
【1】if语句里，条件要清晰。尽量用括号，如果不喜欢，说明您没经验。
if (s == null || t == null || s.length() < t.length()) 错。
应该写成 if ((s == null) || (t == null) || (s.length() < t.length()))
【2】if语句，一定要有 else结尾; case一定要有default
而且，多次矢量 s.length()，时间复杂度很高的。 | r******l
发帖数: 10760 | 8 if一定要else这个太搞了，这是哪家公司啊？
【在 R*********4 的大作中提到】
: 你的编程习惯，在大多数公司里都是要挂的。
: 比如这个
: 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];
: }
| N***t
发帖数: 161 | 9
这样的公司一定很闷吧？
【在 R*********4 的大作中提到】
: 你的编程习惯，在大多数公司里都是要挂的。
: 比如这个
: 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];
: }
| S*******C
发帖数: 822 | 10 leetcode上几乎所有的高分答案都是我这种写法，难道这么多刷题高手都错了？
【在 R*********4 的大作中提到】
: 你的编程习惯，在大多数公司里都是要挂的。
: 比如这个
: 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];
: }
| | | S*******C
发帖数: 822 | 11 这题不是找几个可以删除的位置，而是说删除之后接着删，所以应该是1而不是2
【在 g******d 的大作中提到】
: s = ABABAA
: t = ABA
: 结果应该是2
: 贪心删除法，得到 1
| d*r
发帖数: 821 | 12 对啊, 就是删除以后接着删, 所以是2
你可以先删后一个ABA
【在 S*******C 的大作中提到】
: 这题不是找几个可以删除的位置，而是说删除之后接着删，所以应该是1而不是2
| S*******C
发帖数: 822 | 13 那就复杂了，怎么做？
【在 d*r 的大作中提到】
: 对啊, 就是删除以后接着删, 所以是2
: 你可以先删后一个ABA
| o********t
发帖数: 31 | 14 用DP才是n^2
),
。。
【在 S*******C 的大作中提到】
: 看了一道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) {
| k***g
发帖数: 166 | 15 他说的if一定要有else之类的话可以无视了，不过编程习惯在面试的时候是得小心点。
感觉leetcode追求的是程序短小精干，在实际工作中不一定合适。比如C++不少高分答
案都是只有new没有delete的
【在 S*******C 的大作中提到】
: leetcode上几乎所有的高分答案都是我这种写法，难道这么多刷题高手都错了？
| m******0
发帖数: 222 | 16 我认为DP很难做，很可能找不到DP解法，如果有的话请贴过来，学习一下。
用递归搜索是可以的，基本思路是每次递归，都记录了之前匹配过的partial的
matching，而且这些matching必须是连续的：
下面的code通过了基本测试：
T = ABA
S = ABABAA, ans=2
S = ABABABAAA, ans=3
S = ABAxxxABA, ans=2
S = ABAxxxABABAA, ans = 3
S = ABAxxxABABAx, ans = 2
(more test cases are welcome... )
string S, T;
// find max matches in S[pos ... end] given previous partial matches:
int search(int pos, vector prevMatch) {
if (pos == S.length()) // search is ended
return 0;
int ans1=-1, ans2=-1, ans3=-1;
// 1. start a new partial match, only when S[pos]==T[0]:
if ( S[pos]==T[0] )
{
ans1 = 0;
auto prev = prevMatch;
prev.push_back( T.substr(0, 1) );
if (prev.back() == T)
prev.pop_back(), ans1++;
ans1 += search(pos+1, prev);
}
// 2. if S[pos] can be put into last partial match:
if ( prevMatch.size() && S[pos] == T[ prevMatch.back().length() ] )
{
ans2 = 0;
auto prev = prevMatch;
prev.back() += T[ prevMatch.back().length() ];
if (prev.back() == T)
prev.pop_back(), ans2++;
ans2 += search(pos+1, prev);
}
// 3. when there's no prev match, we have the option to ignore S[pos]
if (prevMatch.size()==0)
{
ans3 = search(pos+1, prevMatch);
}
// if none of above 3 conditions were met, it's invalid search, reutrn 0
if (ans1+ans2+ans3 == -3) return 0;
return max(ans3, max(ans1, ans2));
}
【在 o********t 的大作中提到】
: 用DP才是n^2
:
: ),
: 。。
| R*********4
发帖数: 293 | 17
(￣▽￣)"，一定要有eles和default。最早我遇到是日产给我们一个项目软件审核特别
提到的，我们也觉得是多余。
因为程序除了强壮，还要健壮，我以前也不理解。
后来，程序如果要升级，要扩大，是非常重要的。发现还有一定道理。
还有case一定要有default也是同样一个道理，有许多很大的项目，开发时都没问题，
都是后续升级的时候，在 else和default这里出现问题。
还有后续人员接管你的代码，常常也会忽视那个 如果没有 else和default的部分。
【在 k***g 的大作中提到】
: 他说的if一定要有else之类的话可以无视了，不过编程习惯在面试的时候是得小心点。
: 感觉leetcode追求的是程序短小精干，在实际工作中不一定合适。比如C++不少高分答
: 案都是只有new没有delete的
| g****v
发帖数: 971 | 18 这个难道不应该是2么？ “s = aabcbdc, t = abc, return 1;” 先删除中间的abc，
然后再从剩下的abdc中删除1个abc。
还是我题目理解有误。
),
。。
【在 S*******C 的大作中提到】
: 看了一道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) {
|
|
