使用递归方法对两个字符串之间的第一个不同字符进行索引

Question

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

具有预期产出的示例：

rFirstDistinctPlace（“小包裹”、“小椒盐卷饼”）->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. 如果字符串相等，则返回-1。
2. 如果其中一个字符串的长度为0或者它们的第一个字符不匹配，则返回0。
3. 否则，返回1+rFirstDistinctPlace(S1.substring(1),S2.substring(1))

演示：

class Main {
    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 (Objects.equals(s1, s2))
            return -1;

        if (s1.length() == 0 || s2.length() == 0 || s1.charAt(0) != s2.charAt(0))
            return 0;

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

输出：

8
0
4
-1

Answer 2

递归解决方案：

>

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

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

如果结果是-1，则返回它，如果是-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迭代这两个字符串，直到它到达其中一个字符串的末尾
  • 如果当前索引处的两个字符串的字符不同，则返回i

  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;
  }