Index of first distinct character between two strings using a recursive method

Tags: , ,



I need to find the index of the first distinct character between two strings using a recursive method.

Examples with expected outputs:

rFirstDistinctPlace(“Little parcels”, “Little pretzels”) -> 8

rFirstDistinctPlace(“Gold shadow”, “gold shadow”) -> 0

rFirstDistinctPlace(“gold”, “golda”) -> 4

rFirstDistinctPlace(“gold”,”gold”) -> -1

Note: I can’t use the .equals() function

The thing I’m struggling with is that I need to return -1 if the strings are equal, otherwise it works fine.

Here’s my code:

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

}

This is the helper method 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;
}

Thank you!

Answer

Recursive Solution:

  • If the two strings are empty, this means they are equal, return -1

  • Else if one of them is empty or the first characters don’t match, return 0

  • Else recur with the substrings, if the result is -1, return it, else return it plus 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;
}

Iterative Solution:

  • Iterate over the two strings using a for-loop until it reaches the end of one of them
    • If the characters of the two strings at the current index are different, return i
  • At the end, if the two strings have different lengths, return i, else return -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;
}


Source: stackoverflow