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

Question

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!

Majed Badawi · Accepted Answer · 2021-03-21 14:25:47Z

4

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

edited Mar 21, 2021 at 14:25

answered Mar 21, 2021 at 13:53

Majed Badawi

28.5k4 gold badges30 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

itailitai Over a year ago

What would be the best way to write this function iteratively?

Majed Badawi Over a year ago

@itailitai I added a possible iterative solution to the answer

itailitai Over a year ago

Amazing. Thanks for the help!

Arvind Kumar Avinash · Accepted Answer · 2021-03-21 13:42:09Z

2

It's not so complex.

Return -1 if the strings are equal.
Return 0 if the length of one of the strings is 0 or if their first characters do not match.
Otherwise, return 1 + rFirstDistinctPlace(s1.substring(1), s2.substring(1)).

Demo:

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

Output:

answered Mar 21, 2021 at 13:42

Arvind Kumar Avinash

81.1k10 gold badges98 silver badges144 bronze badges

1 Comment

itailitai Over a year ago

Thanks, but I'm not allowed to use .equals()

Collectives™ on Stack Overflow

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

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related