java - 使用递归方法在两个字符串之间第一个不同字符的索引

Question

我需要使用递归方法找到两个字符串之间第一个不同字符的索引。

具有预期输出的示例:

rFirstDistinctPlace("Little parcels", "Little pretzels") -> 8

rFirstDistinctPlace("Gold shadow", "gold shadow") -> 0

rFirstDistinctPlace("gold", "golda") -> 4

rFirstDistinctPlace("gold","gold") -> -1

注意:我不能使用 .equals() 函数

我遇到的问题是，如果字符串相等，我需要返回 -1，否则它会正常工作。

这是我的代码:

    public static int rFirstDistinctPlace (String s1, String s2) {  
    if (smallestString(s1,s2).length()==0){
            return 0;
    }
    if(s1.charAt(0)!=s2.charAt(0))
        return rFirstDistinctPlace(s1.substring(0,0),s2.substring(0,0));

    return 1+rFirstDistinctPlace(s1.substring(1),s2.substring(1));

}

这是辅助方法smallestString:

    public static String smallestString (String s1, String s2){
    if(s1.length()>s2.length()){
        return s2;
    }
    else if (s2.length()>s1.length()){
        return s1;
    }
    else
        return s1;
}

谢谢!

Answer 1

递归解决方案:

• 如果两个字符串为空，则表示它们相等，返回-1

• 否则，如果其中一个为空或第一个字符不匹配，则返回 0

• 否则与子串循环，如果结果为-1，则返回，否则返回加上1

public static void main(String[] args) {
    System.out.println(rFirstDistinctPlace("Little parcels", "Little pretzels")); //8
    System.out.println(rFirstDistinctPlace("Gold shadow", "gold shadow")); //0
    System.out.println(rFirstDistinctPlace("gold", "golda")); //4
    System.out.println(rFirstDistinctPlace("gold","gold")); //-1
}
public static int rFirstDistinctPlace (String s1, String s2) {
    if(s1.isEmpty() && s2.isEmpty()) return -1;
    else if (s1.isEmpty() || s2.isEmpty() || s1.charAt(0) != s2.charAt(0)) return 0; 
    int index = rFirstDistinctPlace(s1.substring(1), s2.substring(1));
    return index == -1 ? index : 1 + index;
}

迭代解决方案:

• 使用 for-loop 遍历两个字符串，直到到达其中一个字符串的末尾
  • 如果当前index处的两个字符串的字符不同，则返回i
• 最后，如果两个字符串的长度不同，返回i，否则返回-1

public static int rFirstDistinctPlace (String s1, String s2) {
    int i = 0;
    for(i = 0; i < s1.length() && i < s2.length(); i++) {
        if(s1.charAt(i) != s2.charAt(i)) {
            return i;
        }
    }
    return s1.length() != s2.length() ? i : -1;
}