时间戳

首页 > 解决方案 > 优化和提高比较字符串的递归算法的速度

java - 优化和提高比较字符串的递归算法的速度

问题描述

以下算法是这样工作的：给定两个字符串，如果字符串彼此相等，则返回 true，而不管它们的元音如何。

“水”和“wtr”=真

“你好”和“hll”=真

“小提琴”和“vln”=假

有一些参数设置到位。它必须递归地解决，而不是迭代地解决。此外，不允许简单地从两个字符串中删除元音并比较它们。

这是我为解决此问题而编写的程序（调用isStringEqual("water", "wtr")）：

给定一个字符串和一个起始索引，这将调用自身，直到找到辅音的索引。如果不存在辅音，则返回 -1。

    static int findNonVowel(String str, int strIndex) {

        if (str.length() == strIndex) return -1;

        if ("aeiouAEIOU".indexOf(str.charAt(strIndex)) == -1) return strIndex;

        strIndex++;
        return findNonVowel(str, strIndex);
    }

现在，这是解决方案的主要部分。

    static boolean isStringEqual(String strA, String strB) {
        return doIsStringEqual(strA, strB, 0, 0);
    }

    static boolean doIsStringEqual(String strA, String strB, int strAIndex, int strBIndex) {
        if (strA.length() > strB.length() && strB.length() == strBIndex && findNonVowel(strA, strAIndex) != -1)         
            return false;

        if (strB.length() > strB.length() && strA.length() == strAIndex && findNonVowel(strB, strBIndex) != -1)         
            return false;

        if (strA.length() == strAIndex || strB.length() == strBIndex) return true;

        if (strA.charAt(strAIndex) != strB.charAt(strBIndex)) {
            strAIndex = findNonVowel(strA, strAIndex);
            strBIndex = findNonVowel(strB, strBIndex);

            if (strA.charAt(strAIndex) != strB.charAt(strBIndex) && (strAIndex != -1  && strBIndex != -1)) {
                return false;
            }
        }

        strAIndex++; strBIndex++;
        return doIsStringEqual(strA, strB, strAIndex, strBIndex);
    }

首先，我们检查其中一个字符串是否大于另一个字符串，并且通过递归，它们是否超过了另一个字符串的长度。这是为了防止像“violinn”和“vln”这样的误报，但仍然允许“violiniii”和“vln”通过findNonVowel。

如果找到的两个字符不匹配，我们会得到每个最接近辅音的索引，并比较它们。如果它们仍然不相等，并且两个字符串都不是起始索引中的元音，则字符串不相等。

我正在寻找一个内存效率更高的解决方案来解决这个问题。我已经研究过子字符串，但据我了解，这会慢得多，因为它们会在每次递归调用时实例化一个新字符串，而这只是在调用相同的方法。

我也愿意对算法本身进行任何改进，无论是简化它，还是修剪任何样板。

标签： javastringrecursionsubstring

解决方案

在递归思考时，问自己以下问题通常很有用：如果我可以以某种方式减少输入，我将如何使用减少输入的子结果来计算当前结果？

当我想到减少字符串时，我首先想到的就是去掉它们的第一个字符。然后想法来了：如果一个字符串以元音开头，我可以跳过它，结果将与丢弃该字符并比较其余字符串相同；如果两个头都是辅音，那么它们必须匹配。此外，如果我们有空字符串，则为基本情况。

这是一个伪代码：

function bool equal(s,z,start_s,start_z): 

    // s starts with a vowel
    if start_s < len(s) and s[start_s].isVowel(): 
        return equal(s,z,start_s+1,start_z)

    // z starts with a vowel
    if start_z < len(z) and z[start_z].isVowel(): 
        return equal(s,z,start_s,start_z+1)

    // no vowels, maybe an empty string?
    if start_s == len(s) or start_z == len(z):
        // if we have an empty string, they should both be empty
        return start_s-len(s) == start_z - len(z)

    // no empty string, no vowels: consonants should match 
    return s[start_s] == z[start_z] and equal(s,z,start_s+1,start_z+1)

该算法在时间上是线性的，在额外内存中是恒定的。

我希望这有帮助！

推荐阅读