时间戳

首页 > 解决方案 > (Java) 如何在没有辅助函数的情况下从不断增加的堆栈帧返回 -1？

java - (Java) 如何在没有辅助函数的情况下从不断增加的堆栈帧返回 -1？

问题描述

我正在做这个一毛钱的递归问题，我们必须返回第一个索引，其中子字符串出现在更大的字符串中。如果没有找到，返回-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;
    }

那么如果它有效，那么问题是什么？问题是整个返回 -1 的东西。它返回正确的子字符串索引，但无效输入不返回 -1。这个递归函数是建立在这样的想法之上的，当它进一步向下遍历子字符串时，它会一起获取和索引，所以如果在“hello”中找不到，它将转到“ello”并在下面塞一个 1 索引它的帽子，因为我们现在知道索引，如果它存在，至少为1。

但问题是，随着堆栈帧的深入，它们会不断增加 1，因此 -1 没有效果。如果我将 s2 设置为“x”之类的东西，它只会返回“4”，即它遍历“hello”子字符串的次数。如果没有一个数字来跟踪堆栈帧，我无法通过说“return -5”或其他什么来使其等于 -1。有没有办法让它遍历整个字符串，不断增加 1，但在最后，如果找不到 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”，它实际上必须在开始而不是结束时才能工作。我只在它有帮助的情况下显示这个。

标签： javarecursionstack-frame

解决方案

存储递归调用的结果，-1如果是则返回-1。

int result = indexOf(s1.substring(1, s1.length()), s2);
return result != -1 ? result + 1 : -1;

推荐阅读