8

Given that 2 strings:

String stringA = "WHATSUP";
String stringB = "HATS";

I want to find out whether each character in stringB H A T S exists in stringA

In a junior approach, the process can be done within a nested for-loop which its computation complexity is O(n^2).

for(int i = 0; i < stringA.length(); i++){
    for(int j = 0; j < stringB.length(); j++){
        if(stringA.charAt(i) == stringB.charAt(j))
            //do something
    }
}

I am looking for a faster solution to solve this problem.

Kone Man
  • 374
  • 1
  • 2
  • 8

1 Answers1

10

There is a linear time algorithm.

  1. Convert your stringA to a hash-set of characters that has O(1) membership testing.
  2. Iterate over each character in stringB.
  3. If one of the characters isn't in your hash-set, the test fails.
  4. If there is no failure, the test succeeds.
recursive
  • 83,943
  • 34
  • 151
  • 241
  • If `stringA` is significantly longer than `stringB,` couldn't the conversion slow down the process in the long run? – Alexander Guyer Aug 05 '16 at 17:39
  • @Nerdizzle: Yes, it's possible for specific cases to be slower using this approach. – recursive Aug 05 '16 at 17:41
  • Couldn't you just create two hashsets and use `containsAll()`? – NullUserException Aug 05 '16 at 17:41
  • @NullUserException: You could do that. It has the same time complexity. – recursive Aug 05 '16 at 17:42
  • You could use a hashset with initial size set at stringA.length() and compaction factor of 1F, then do a Collections.addAll(hashset,stringA.toCharArray()), that would give you your hashset w/o the wait of having to expand it – Sameer Puri Aug 05 '16 at 17:43
  • 1
    Interesting approuch. I would be interested if the use of a bitset might improve this. Where either the value of the char, or the position in a predefined alphabet/charScheme determines the position/offset in the BitSet. If there are limited characters allowed (e.g. only alphabet for example) it might be a bit more effecient than the use of a HasSet. – n247s Aug 05 '16 at 17:47
  • I understand the process time of "string to hashset" conversion is O(1), but it is pretty long in practical case. (I measure the process time by comparing the time before and after the conversion). Is there a problem with my measuring method? Or this is a theory and my concern is not valid? – Kone Man Aug 06 '16 at 16:03
  • String to hashset is not O(1). It's proportional to the length of the string. After the string is constructed, membership tests are O(1). This analysis is theoretical, and would be most observable with very large strings. (10000 characters or more) To offer practical performance advice, we'd need to know more about your use case. – recursive Aug 06 '16 at 16:34