comparing between 2 strings characters in a recursive way

[Adm666]

i tend to make a method which compares between 2 strings, str1 and str2 and should return true in the terms:
-every character in str1 must show up in str 2 at least once or more and in the same order
-str2 must be the same length or longer than str1
-str2 should not contain any character that isn't in str1
otherwise it should reture false.
for example if str1=abbcd and str2=abbcccd it should return true
if str1=abbcd and str2=abcd it should return false
and im trying to make it in a recursive way and without loops
and i ended up doing this...

public static boolean compare (String s, String t)
    {
        boolean result;
            if (stringSum(t, 0)>=stringSum(s, 0)){
                return true;
            }
        return false;
    }

    private static int stringSum(String s, int i)
    {
        if (i==s.length())
            return 0;
        return ((int)s.charAt(i)+ stringSum (s, i+1));
    }

im stuck without finding away to do it....may i have someone's guidance ?

[JamesCherrill]

Doing it by comparing characters implies a loop or recursion that maintains a current index for each string - it's going to be quite fiddly to get right.
As a completely different approach... if you write a method to remove all the duplicated consecutive chars from string2 then the result should be equal to string1. That's a much simpler task for a little recursive method.

ps (int)s.charAt(i)+ stringSum (s, i+1)
There's no need for the int cast. Java chars are 16 bit numeric values and can be added directly to an int, giving an int result.

[Adm666]

thanks for the the cast notice !

Doing it by comparing characters implies a loop or recursion that maintains a current index for each string - it's going to be quite fiddly to get right.
As a completely different approach... if you write a method to remove all the duplicated consecutive chars from string2 then the result should be equal to string1. That's a much simpler task for a little recursive method.
and the thing is, i can't use any other than those 4 string methods : length() charAt() substring() equals() in this method... so i can't make anychange to the strings the method gets.
i thought of doing it with a sequential search, do i need an array to do it that way?
like if i wanted to find a number within an array i would od it like this :

boolean recFind (int[]a, int i, int x)
if (i==a.length)
    return false;
if (a[i] ==x)
    return true;
return recFind (a, i+1, x);

where X is the number that im looking for and "i" gonna set it as zero when i call recFind from another method
do i need to put the characters of the strings in arrays and start to compare each indexs? but then it'll take so much memory and time complexity ..

[JamesCherrill]

tried the de-duplication method, and discovered the idea doesn't work if the first string has consecutive duplicated characters, so forget that. Looking at it again, and remembering the s1 may have consecutive repeated letters, I now think this is going to require a really horrible algorithm.

Anyway...
no need to worry about changing the strings the method gets. All Java strings are immutable so there is no way to change them. You can of course create new strings, which is what substring() does.

Do you have to do this recursively, without loops or is that just an idea? IMHO it's a natural for loops, and a poor fit for recursion.

[Adm666]

Do you have to do this recursively, without loops or is that just an idea?

i need to do it recursively without loops.
i also tried this...but i get outOfBounds error

public static boolean compare(String s,String t)
        {
            if (s.equals(t))
                return true;
            if (t.length()<s.length())
                return false;
            if (stringChar(s, t, 0, 0)==true)
                return true;
            return false;
        }

    private static boolean stringChar(String s, String t, int i, int j)
    {

        if (i==s.length())
            return true;
        if (s.charAt(i)==t.charAt(j)){
            return stringChar (s, t, i+1, j+1);
        }
        else if (s.charAt(i)!=t.charAt(j))
            return stringChar(s, t, i, j+1);
            else
        return false;
    }

[Adm666]

making it to go through every character of str1 and compare it to str2, if equal then continue to the next char, if not equal then raise the str2's "char index" counter which is "j" and compare it , if not then (recursively) repeat the check, if it reaches the end of str2 without finding the equal char then return false.
but what if there's an additional character in str2 that is not included in str1.....that should return false too
im sorry im quite a newbie in programming trying to learn it... thanks for your paitence !

[JamesCherrill]

Hi Adam
That's what I thought at first, but consider the sample data
str1=abbcd and str2=abbcccd
when processing the first b in str1 you will consume all the b's in str2, then move on to the second b in str1 and find no match...

[JamesCherrill]

but i get outOfBounds error

When you get an exception ALWAYS post th ecomplete message and the line where it was thrown. Knowing the exact line, and the index value, will make it easy to see what the problem is.

and a tiny point, but it always bugs me to see it...
if (stringChar(s, t, 0, 0)==true)
stringChar(s, t, 0, 0) returns true or false.
true == true is true
false == true is false
ie adding == true to a boolean does exactly nothing execpt clutter/confuse the code.

[Adm666]

so i've reached this...

public static boolean isTrans(String s,String t)
        {
            if (s.equals(t))
                return true;
            if (t.length()<s.length())
                return false;
            return stringChar(s, t, 0);

        }

    private static boolean stringChar(String s, String t, int i)
    {

        if (i==t.length())
            return true;
        if (s.charAt(i)==t.charAt(i)){
            return stringChar (s, t, i+1);
        }
        else if (s.charAt(i)!=t.charAt(i))
            return stringChar(s, t.substring(1), i);
            else
        return false;
    }

for str1= abbcd and str2=abbcccdd
i get this error...
java.lang.StringIndexOutOfBoundsException:
String index out of range: 5 (in java.lang.String)

[JamesCherrill]

This is a really interesting challenge! To cope with repeated consecutive chars I think you have to break each string up into blocks of repeated (1 or more) chars and compare those (the block from str2 must be the same char and as long or longer than the block from str1).
I tried this using loops and it seems to work (?). If you agree it works then maybe it will confirm some ideas towards a recursive solution. (?)

So first I created a small immutable class to define a block of a repeated characters. It has a factory static method to create a block from an input String starting at a specified index, and a method to test if one block is the same char and at least as long.

class RepeatedChar {

    final char c;
    final int length;

    public RepeatedChar(char c, int length) {
        this.c = c;
        this.length = length;
    }

    public boolean contains(RepeatedChar rc1) {
        return c == rc1.c && length >= rc1.length;
    }

    public static RepeatedChar from(String s, int startIndex) {
        char c = s.charAt(startIndex);
        int length = 1;
        for (int i = startIndex + 1; i < s.length(); i++) {
            if (s.charAt(i) != c) break;
            length++;
        }
        return new RepeatedChar(c, length);
    }
}

Now using that its easy to loop along the two strings getting the blocks and comparing them

    boolean isDup(String str1, String str2) {
        int i1 = 0, i2 = 0;
        while (i1 < str1.length() && i2 < str2.length()) {
            RepeatedChar r1 = RepeatedChar.from(str1, i1);
            RepeatedChar r2 = RepeatedChar.from(str2, i2);
            if (! r2.contains(r1)) return false;
            i1 += r1.length;
            i2 += r2.length;
        }
        return i1 == str1.length() && i2 == str2.length();
    }

This seems to work for me given a variety of test data, maybe you can confirm?

JC

[JamesCherrill]

i get this error...
java.lang.StringIndexOutOfBoundsException:
String index out of range: 5 (in java.lang.String)

That's a start. Almost certainly an incorrect parameter in a call to String's substring method. Now if you look down the stack dump you will find 1 or 2 lines below that the line number in your code where the String method was called, and that's the line you need to look at.

[Adm666]

thanks a bunch for the help man ! and you gave me lots of ideas of how to complete my project that im working at.
but still i don't want to make an entire class just for comparing those strings i need to include this in a single class within my project..
And i've come pretty close to the solution.
just....a liiiittle thing left to correct is the situation where str2 would have a char that is not included in str1 which should return false.
but it return true..

public static boolean isTrans(String s,String t)
        {
            if (s.equals(t))
                return true;
            if (t.length()<s.length())
                return false;
            return stringChar(s, t);

        }

    private static boolean stringChar(String s, String t)
    {
        if (s.length()>t.length())
            return false;
        if (s.length()==0)
            return true;
        if (s.charAt(0)==t.charAt(0)){
            return stringChar (s.substring(1), t.substring(1));
        }
         else if (s.charAt(0)!=t.charAt(0))
            return stringChar(s, t.substring(1));
            else
        return false;
    }

trying ot figure out how..
Agina thanks alot for your paitence with me ! in other sites they kicked me already from the begginning when i asked my question and deleted my topic saying " we don't give answers we only guide" lol...

[AssertNull]

just....a liiiittle thing left to correct is the situation where str2 would have a char that is not included in str1 which should return false.

That may or may not be a little thing.

This is one of those problems where I have a bit of a problem figuring out exactly what the rules and assumptions are, which you have to nail down prior to coding. If I take a very strict literal interpretation of the rules, as far as I can tell, you compare the lengths of the two strings and if str1 is longer than str2, you return false. After that you strip each string of all occurrences of any letter after the first incidence of that letter. Then you compare the two stripped strings and return true if they're the same, false otherwise. Thus

if str1=abbcd and str2=abcd it should return false

fails because str2 is too short, not because it contains fewer b's than str1. That's my STRICT interpretation of these words...

-every character in str1 must show up in str 2 at least once or more and in the same order

I doubt my strict reading is the actual intent though. If it is, then if you change str2 to "abcda", it should return true. Pretty sure your code returns it as false.

The solution, in my opinion, is to give a whole bunch of test cases and their proper output, beyond the two you gave, to make it crystal clear what the rules are. Sometimes the English languge is not precise enough. I'm seeing James trying to figure out where consecutive letters occur, so there might be ANOTHER interpretation out there.

It's essential to figure out good test cases that hit every possible false positive and false negative. Do you have a list of cases you plan to feed this program, along with the expected results? Just making a comment on the general methodology, not the specific coding here.

[JamesCherrill]

i don't want to make an entire class just for comparing those strings i need to include this in a single class within my project..

It's a common beginner mistake to avoid defining a small class because it seems somehow too complicated. Just look at the Java API to see how common it is to define a class because that makes the code overall simpler. Remember also you can define a class inside another class, especially if it's only going to be used in the outer class.
Anyway, it looks like you have this under control now, so I'll drop out unless you hit a new snag.

in other sites they kicked me already from the begginning when i asked my question

Here at DW we pride ourselves on being beginner-friendly, and taking the time to discuss ideas. All we ask is that you at least match the effort we are putting in - and you certainly have done that.
Tell your friends!

[Adm666]

Hey AssertNull

That's my STRICT interpretation of these words...
Im sorry for my childish way of thinking but i can't get the message... is it impossible to do it without arrays while still sticking with not using other of the 4 string methods i've mentioned or...?
I doubt my strict reading is the actual intent though. If it is, then if you change str2 to "abcda", it should return true. Pretty sure your code returns it as false.
if you meant that with str1 being "abbcd" then no it shouldn't return true cuz the last "a" in str2 tthat u suggested isn't in the right order plus it showed up more than the times "a" did in str1
Do you have a list of cases you plan to feed this program
and yes i do try to have some list checking the possibilities but my case is that im a newbie in programming.....and i can't afford to sign in a course to do it at the moment so im trying to get the most of it meanwhile having my freetime

James :>

It's a common beginner mistake to avoid defining a small class because it seems somehow too complicated.
Well thats one sure thing I really saw it kinda complicated too, but still though in the task itself im trying to accomplish demanding to do it all together in a single class and with only 2 methods... public and private...i think i'll give it a rest...i've been studying from the morning.. and its nearly evening im surprised myself that i've understood most of the basics all the basics in less than a week. recursion really is a one damn obsticle im stuck at
Here at DW we pride ourselves on being beginner-friendly
These words really earned my deepest respect and im very thankful to have encountered this community likewise yourself being a huge help !

[Adm666]

sorry i qouted accidently the whole texts... my eyes are tired hehe

[Adm666]

Okay...so far im stuck here....

private static boolean stringChar(String s, String t, char j)
    {
        if (s.length()>t.length())
            return false;
        if (s.length()==0&&t.length()!=0)
            if (t.charAt(0)!=j)
                return false;
            else
                return stringChar(s, t.substring(1), j);
        if (s.length()==0)
            return true;
        if (s.length()==1)
            j=s.charAt(0);
        if (s.charAt(0)==t.charAt(0)){
            return stringChar (s.substring(1), t.substring(1), j);
        }
         else if (s.charAt(0)!=t.charAt(0))
            return stringChar(s, t.substring(1), j);
            else
           return false;
    }

by using this additional "J" char variable the issue of returning true to those:
str1=abcd and str2=abcds (which should be false)
is solved. but can't find a way to see what if this "s" char was somewhere in the middle...

[AssertNull]

Perhaps you can search the string s for the character j using the indexOf function provided by Java's String class? It will return the index of 's' (for "abcds", that would be 4. For a string that did NOT contain 's', it would return -1 (ie not found)). I'm not 100% sure of what you're doing here, but if the problem is determining whether a character is in a string, that function will do the job.

https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#indexOf-int-

[Adm666]

Perhaps you can search the string s for the character j using the indexOf function provided by Java's String class?

sadly no ;( i can't use that function im limited by only 4 : length() charAt() equals() substring()