Question 2. String Containing Problem

Question:  there are two string A & B which only contain upper case English alphabets. B has smaller length than A. How to quickly decide whether all the characters in B are contained in A. For exmaple,

String A : ABCDEFGHLMNOPQRS

String B : DCGSRQPO

Your method take A and B as input and should return true because All characters in B appeared in A too.

String A : ABCDEFGHLMNOPQRS

String B : DCGSRQPZ

Your method take A and B as input and should return false because character 'Z' appeared in B but in A.

 

My thought: It's a gernal question like checking whether a word spelling is correct. We can just setup a HashSet of all the characters appeared in A and then go through characters in B to check whether they are in the HashSet. However since the characters are limited to English alphabets, we can a boolean array of length 26 or even use the lowest 26 bits of an Integer to record the appearance of each alphabet

Although boolean array may waste some space ( depends on JVM implementation of boolean type ) , but I think array access should be faster than bit operation

 

Java Implementation:

public class StringContaining {

	public static void main(String[] args) {
		BooleanArray set1 = new BooleanArray();
		BitsArray set2 = new BitsArray();
		
		assert contains("ABCDEFGHLMNOPQRS" , "DCGSRQPO" , set1);
		assert contains("ABCDEFGHLMNOPQRS" , "DCGSRQPO" , set2);
		
		assert !contains("ABCDEFGHLMNOPQRS" , "DCGSRQPZ" , set1);
		assert !contains("ABCDEFGHLMNOPQRS" , "DCGSRQPZ" , set2);

	}
	
	
	public static boolean contains (String sa, String sb , CharHashSet set) {
		
	    int i = 0;
	    int size = sa.length();
	    for (; i < size; i ++ ) {
	    	set.add(sa.charAt(i));
	    }
	    
	    for ( i = 0 , size = sb.length() ; i < size ; i ++ ) {
	    	if (! set.contains(sb.charAt(i))) return false;
	    }
		
	    return true;
		
	}
	
	public interface CharHashSet {
		public void add(char c);
		
		public boolean contains ( char c);
	}
	
	public static class BooleanArray implements CharHashSet{

		private boolean[] exists = new boolean[26];
		
		@Override
		public void add(char c) {
			exists[c - 'A'] = true;
		}

		@Override
		public boolean contains(char c) {
			return exists[c-'A'];
		}
	}
	
	public static class BitsArray implements CharHashSet{
         
		private int exists;
		
		@Override
		public void add(char c) {
			exists |= 1 << (c - 'A');
			
		}

		@Override
		public boolean contains(char c) {
			
			return ( exists & (1 << (c - 'A')) ) > 0;
		}
		
	}
	

}