The Fake Geek's blog: Find Common Characters
Write a program that gives count of common characters presented in an array of strings..(or array of character arrays)
For eg.. for the following input strings..
aghkafgklt
dfghako
qwemnaarkf
The output should be 3. because the characters a, f and k are present in all 3 strings.
Note: The input strings contains only lower case alphabets
My solution is based on the same idea as all other solutions. The map size is the number of unique characters in the first string in the array. Because we have to go through the array and check every string, the time complexity is O(mn), where m is the average string length in the array and n is the array length. I don't think we can beat this complexity, can we?
http://www.careercup.com/question?id=6283084039192576
Write a program that gives count of common characters presented in an array of strings..(or array of character arrays)
For eg.. for the following input strings..
aghkafgklt
dfghako
qwemnaarkf
The output should be 3. because the characters a, f and k are present in all 3 strings.
Note: The input strings contains only lower case alphabets
My solution is based on the same idea as all other solutions. The map size is the number of unique characters in the first string in the array. Because we have to go through the array and check every string, the time complexity is O(mn), where m is the average string length in the array and n is the array length. I don't think we can beat this complexity, can we?
public
int
getNumOfCommonChars(String[] inputs) {
if
(inputs ==
null
|| inputs.length < 2)
return
0;
HashMap<character,integer
> hm =
new
HashMap<
>();
for
(
int
i = 0; i < inputs[0].length(); i++) {
if
(hm.containsKey(inputs[0].charAt(i)))
continue
;
else
hm.put(inputs[0].charAt(i), 1);
}
for
(
int
i = 1; i < inputs.length; i++) {
String tmp = inputs[i];
for
(
int
j = 0; j < tmp.length(); j++) {
if
(!hm.containsKey(tmp.charAt(j)))
continue
;
if
(hm.
get
(tmp.charAt(j)) == i + 1)
continue
;
hm.put(tmp.charAt(j), hm.
get
(tmp.charAt(j)) + 1);
}
}
int
count = 0;
for
(Integer ele : hm.values()) {
if
(ele == inputs.length){
count++;
}
}
return
count;
}
static public void commonCharracters(String[] strings) {
int[] alphabets = new int[26];
for (String string : strings) {
for (int i = 0; i < string.length(); i++) {
char c = string.charAt(i);
if (!string.substring(0, i).contains(c + "")) {
alphabets[c - 97]++;
}
}
}
for (int i = 0; i < alphabets.length; i++) {
if (alphabets[i] == strings.length) {
System.out.println((char) (i + 97));
}
}
}
Read full article from The Fake Geek's blog: Find Common Characters