(Java) 如何在没有辅助函数的情况下从不断递增的堆栈帧中 return -1?
(Java) How to return -1 from constantly incrementing stack frames without helper function?
我正在做这个一毛钱一打的递归问题,因此我们必须 return 第一个索引,其中子字符串出现在较大的字符串中。如果没有找到,return-1。不鼓励辅助函数。
indexOf("Hello", "Lo") --> 3
,因为“lo”首先出现在索引 3 处。
indexOf("Hello", "H") --> 0
,因为“H”首先出现在索引 0 处。
indexOf("Hello", "x") --> -1
,因为“x”根本没有出现
好消息是:我已经弄明白了!
public static int indexOf(String s1, String s2) {
//Invalid cases: empty string or invalid input, where s1 length is less than the substring length.
//Base case: If s1, sliced to the same length as s2, equals s2, then return 0.
//Otherwise, return recursively + 1.
if (s1.length() == 0 | s1.length() < s2.length()) {
return -1;
} else if (s1.substring(0, s2.length()).equals(s2)) {
return 0;
}
return indexOf(s1.substring(1, s1.length()), s2) + 1;
}
所以如果它有效,问题是什么?问题是整个 returning -1 事情。它 return 是子字符串的正确索引,但无效输入不会 return -1。这个递归函数是建立在这个想法之上的,当它进一步向下遍历子字符串时,它会与它一起获取和索引,所以如果在“hello”中找不到,它会转到“ello”并在下面塞入一个 1 索引它的帽子,因为此时我们知道索引(如果存在)将至少 1.
问题是,随着堆栈帧的深入,它们会不断递增 1,因此 -1 不起作用。如果我将 s2 设置为类似“x”的东西,它只是 returns “4”,它遍历“hello”的子字符串的次数。没有数字来跟踪堆栈帧,我无法通过说“return -5”或其他任何方式使它等于 -1。有没有办法让它遍历整个字符串,不断递增 1,但不知何故在最后,return 如果找不到 s2 则为 -1?
硬编码版本(我最喜欢的递归策略):
public static int indexOf(String s1, String s2) {
if (s1.length() == 0 | s1.length() < s2.length()) {
return -1;
} else if (s1.substring(0, s2.length()).equals(s2)) {
return 0;
} else if (s1.substring(1, 1 + s2.length()).equals(s2)) {
return 0 + 1;
} else if (s1.substring(2, 2 + s2.length()).equals(s2)) {
return 0 + 1 + 1;
} else if (s1.substring(3, 3 + s2.length()).equals(s2)) {
return 0 + 1 + 1 + 1;
} else if (s1.substring(4, 4 + s2.length()).equals(s2)) {
return 0 + 1 + 1 + 1 + 1; //what the other function returned + 1
}
return -1;
}
它以这种硬编码的方式绝对完美地工作。我意识到问题是最后一个“return -1”,它实际上必须在开始而不是结束才能工作。我只显示它以防它有帮助。
存储递归调用的结果,如果是 -1
.
,则 return -1
int result = indexOf(s1.substring(1, s1.length()), s2);
return result != -1 ? result + 1 : -1;
我正在做这个一毛钱一打的递归问题,因此我们必须 return 第一个索引,其中子字符串出现在较大的字符串中。如果没有找到,return-1。不鼓励辅助函数。
indexOf("Hello", "Lo") --> 3
,因为“lo”首先出现在索引 3 处。
indexOf("Hello", "H") --> 0
,因为“H”首先出现在索引 0 处。
indexOf("Hello", "x") --> -1
,因为“x”根本没有出现
好消息是:我已经弄明白了!
public static int indexOf(String s1, String s2) {
//Invalid cases: empty string or invalid input, where s1 length is less than the substring length.
//Base case: If s1, sliced to the same length as s2, equals s2, then return 0.
//Otherwise, return recursively + 1.
if (s1.length() == 0 | s1.length() < s2.length()) {
return -1;
} else if (s1.substring(0, s2.length()).equals(s2)) {
return 0;
}
return indexOf(s1.substring(1, s1.length()), s2) + 1;
}
所以如果它有效,问题是什么?问题是整个 returning -1 事情。它 return 是子字符串的正确索引,但无效输入不会 return -1。这个递归函数是建立在这个想法之上的,当它进一步向下遍历子字符串时,它会与它一起获取和索引,所以如果在“hello”中找不到,它会转到“ello”并在下面塞入一个 1 索引它的帽子,因为此时我们知道索引(如果存在)将至少 1.
问题是,随着堆栈帧的深入,它们会不断递增 1,因此 -1 不起作用。如果我将 s2 设置为类似“x”的东西,它只是 returns “4”,它遍历“hello”的子字符串的次数。没有数字来跟踪堆栈帧,我无法通过说“return -5”或其他任何方式使它等于 -1。有没有办法让它遍历整个字符串,不断递增 1,但不知何故在最后,return 如果找不到 s2 则为 -1?
硬编码版本(我最喜欢的递归策略):
public static int indexOf(String s1, String s2) {
if (s1.length() == 0 | s1.length() < s2.length()) {
return -1;
} else if (s1.substring(0, s2.length()).equals(s2)) {
return 0;
} else if (s1.substring(1, 1 + s2.length()).equals(s2)) {
return 0 + 1;
} else if (s1.substring(2, 2 + s2.length()).equals(s2)) {
return 0 + 1 + 1;
} else if (s1.substring(3, 3 + s2.length()).equals(s2)) {
return 0 + 1 + 1 + 1;
} else if (s1.substring(4, 4 + s2.length()).equals(s2)) {
return 0 + 1 + 1 + 1 + 1; //what the other function returned + 1
}
return -1;
}
它以这种硬编码的方式绝对完美地工作。我意识到问题是最后一个“return -1”,它实际上必须在开始而不是结束才能工作。我只显示它以防它有帮助。
存储递归调用的结果,如果是 -1
.
-1
int result = indexOf(s1.substring(1, s1.length()), s2);
return result != -1 ? result + 1 : -1;