Wednesday, July 30, 2014

Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?

Problem

Given two strings str1 and str2, write code to find out if all non-unique elements in str2 are in str1?

Solution

Method 1 - Using hashset on str2 and boolean array or hashset on str2
Break down the problem into two tasks.

i) Finding the non-unique i.e. repeating elements in str 1. Hashing can be used for this purpose.

ii) Finding if all the characters hashed in the first string are available in the second string. You can use a bool flag array for this purpose

Java code
public static Set<String> getNonUniqueChar(String str1, String str2){
 HashMap<Character, Integer> visit = new HashMap<Character, Integer>(); // find the non-unique characters
    HashSet<Character> visit2 = new HashSet<Character>(); // put the st1 chars into to hashset
    for (int i=0; str2.length; i++) {
  char c = str2.charAt(i);
  if(visit.containsKey(c)){
   Integer charCount = visit.get(c);
   visit.put(c,charCount++);
  }else
   visit.put(c,1);//initially char count is 1
 }
         
    for (i=0; i < str1.length; i++){
  char c = str1.charAt(i);
        if(!visit2.contains(c))
   str1.put(c);
 }
 //get all the elements where count is greater than 1
 List<String> nonUniqueCharsinS2 = new ArrayList<String>();
 for(Character c : visit.keys()) {
  if(visit.get(c) > 1)
   nonUniqueCharsinS2.add(c);
 }
 
 //iterate on s1 set to get all the elements
 Set<String> answer = new HashSet<String>();
    for (Character c : nonUniqueCharsinS2 )
         if(visit2.contains(c))
   answer.add(c);
     
  return answer;
}

Time complexity - O(n)
Space complexity - O(n)

0 comments:

Post a Comment