Comparing two strings to see if string 2 is inside string 1

Question

Here is what I have to do:

Write a function scramble(str1,str2) that returns true if a portion of str1 characters can be rearranged to match str2, otherwise returns false.

For example:

str1 is 'rkqodlw' and str2 is 'world' the output should return true.

str1 is 'cedewaraaossoqqyt' and str2 is 'codewars' should return true.

str1 is 'katas' and str2 is 'steak' should return false.

Only lower case letters will be used (a-z). No punctuation or digits will be included. Performance needs to be considered

public class Scramblies {
    public static boolean scramble(String str1, String str2) {
        String temp = str1;
        int count = 0;
        boolean result = true;
        for(int i=0 ; i<str2.length() ; i++){
            char c = str2.charAt(i);
            if(temp.contains(String.valueOf(c))){
                temp = temp.replaceFirst(String.valueOf(c), "");
                count++;
            }
        }
        if (count == str2.length()){
            result = true;
        } else {
            result = false;
        }
        return result;
    }
 }

My code works perfectly, but the only problem now is efficiency. I am tested against how long it takes to finish the final test class, which times out. I get this:

Process was terminated. It took longer than 10000ms to complete

How can this code be made more efficient to achieve the same result?

I have rolled back the last edit. Please see What to do when someone answers. — Mast
– Mast ♦, Commented Mar 29, 2016 at 13:11

Tunaki · Accepted Answer · 2016-04-10 12:30:15Z

The problem with your approach is that you're traversing the second String as many times as there are elements in the first String with the replaceFirst call (which also involves a regular expression).

Also, this has nothing to do with performance, but you could just use

return count == str2.length();

instead of the long, and so more difficult to read,

boolean result = true;
if (count == str2.length()){
    result = true;
} else {
    result = false;
}
return result;

You can tackle this problem a lot more effectively by taking advantage of the fact that only lower case letters will be used (a-z). Consider the following approach:

We know that there are 26 lower case characters. Let us create an array of 26 values int[] array = new int[26];.
For each character c of the second String, we increment the value stored in the array at the position c - 'a': this corresponds to the alphabetical position of the character (based from 0: 'a' -> 0, 'b' -> 1, ..., 'z' -> 25).
Then for each character c of the first String, we decrement the value stored at the alphabetical position.
Finally, if at the end of this process, we end up with at least one value that is strictly positive, we know that the second String wasn't contained in the first one. This is because it means that we encountered a character in str2 more times than it was in str1 (it was incremented more times than it was decremented).

A sample implementation of this approach would be:

public static boolean scramble(String str1, String str2) {
    int[] array = new int[26];
    for (char c : str2.toCharArray()) {
        array[c - 'a']++;
    }
    for (char c : str1.toCharArray()) {
        array[c - 'a']--;
    }
    for (int value : array) {
        if (value > 0) {
            return false;
        }
    }
    return true;
}

You can test it with

public static void main(String[] args) {
    System.out.println(scramble("rkqodlw", "world")); // prints "true"
    System.out.println(scramble("cedewaraaossoqqyt", "codewars")); // prints "true"
    System.out.println(scramble("katas", "steak")); // prints "false"
}

Hi Tunaki, thanks for your response. I think I am missing something. Why would I need to do array[c - "a"]? — Archeofuturist
– Archeofuturist, Commented Mar 29, 2016 at 13:47
@SimonAugustus The character c, expressed as an int, is its ASCII value. The character 'a' is 97. You can confirm that by having System.out.print((int) 'a');. All others lowercase letter are after that one. b is 98, etc... up to z which is 122. The trick here is to shift all those values by 97 to have it 0-based. — Tunaki
– Tunaki, Commented Mar 29, 2016 at 13:53
@SimonAugustus Notice that it's 'a', not "a". The difference between single and double quotes is important – one is a char, which supports - and can be used as an int, and the other is a String which can't. — anon
– anon, Commented Mar 29, 2016 at 21:12

Soudipta Dutta · Accepted Answer · 2019-05-03 12:26:41Z

This is comparatively easy when we use Java streams with anyMatch. Let's look at this program.

public class Test2 {
    public static void main(String[] args) {

        String a = "Gina Gini Protijayi Soudipta";
        String b = "Gini";

        System.out.println(WordPresentOrNot(a, b));
    }// main

    private static boolean WordPresentOrNot(String a, String b) {
    //contains is case sensitive. That's why,change it to upper or lower case. Then check
        // Here we are using stream with anyMatch
        boolean match = Arrays.stream(a.toLowerCase().split(" ")).anyMatch(b.toLowerCase()::contains);
        return match;
    }

}

BitShifter · Accepted Answer · 2016-03-30 16:54:45Z

-1

Another method would be to sort all the letters in both strings. If the first value in string 1 doesn't match the first value in string 2, skip it. If the first value in both string 1 and string 2 match, skip both. If you run out of string 1 while there are still values in string 2 there is no match. If you consume all of string2's values, you match.

edited Mar 30, 2016 at 16:54

answered Mar 29, 2016 at 17:59

BitShifter

991 bronze badge

\$\begingroup\$ Someone suggested an edit saying that this algorithm wouldn't match if you had repeated letters and used the example "aaab" and "ab" as the strings. This algorithm would match, the first time through, you would trim the first a. the second and third time through, s1 would have 'a' as the first letter and s2 would have 'b' so you drop the 'a's from s1. the 4th time through the top would be 'b'. Now all input has been consumed from s2, so you match. They also commented on run time and said nlog(n) where n is length of s1. Close, nlog(n) + m*log(m) + n. Have to sort both strings. \$\endgroup\$

BitShifter
– BitShifter

2016-03-30 16:59:51 +00:00
Commented Mar 30, 2016 at 16:59

Add a comment |

Stack Exchange Network

Comparing two strings to see if string 2 is inside string 1

3 Answers 3

You must log in to answer this question.

Hot Network Questions

Comparing two strings to see if string 2 is inside string 1

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions