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 str2Break 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