Find max common string at the beginning of a string list
e.g.
Cases:
"abcd", "abbx", "abxdad", "abddeed" -- return "ab"
"dabcd", "xabbx", "dabxdad", "babddeed" -- return ""
"" , "abd", "abdd", "abxd", "abxd", "abad" -- return ""
Given a string list with n strings, calculate the max common string
- Compare each character in corresponding position with the character in first string until the mismatch happens
- Set the position as max comparing length next term
- Loop through all strings
- Copy first matching length characters and return
C Language
#include <iostream>
using namespace std;
char *get_max_comm_str_DFS(char *strlist[], int l)
{
static char comm_str[256];
int shortest_len = 256;
int i, j;
char c0, c1;
for(i = 0; i < l; ++i){
j = 0;
while(j < shortest_len){
c0 = strlist[0][j];
c1 = strlist[i][j];
if(c0 != c1 || c0 == '\0' || c1 == '\0'){
shortest_len = j;
break;
}
j++;
}
}
for(i = 0; i < shortest_len; ++i){
comm_str[i] = strlist[0][i];
}
comm_str[i] = '\0';
return comm_str;
}
int main(int argc, char* argv[])
{
char *test_cases[][5] = {
{"abcd","abcdfed","abcdxd","abcdd","abcdpd"}, // should return abc
{"abcd","abcfed","","abcdd","abcpd"}, // should return ""
{"a","a","abcxd","abcdd","abcpd"}, // should return ""
{"xabcd","yabcfed","jabcxd","kabcdd","abcpd"} // should return ""
};
for(int i = 0; i < 4; ++i){
cout << "Test case #" << i << " -- max common string at the beginning: " << get_max_comm_str_DFS(test_cases[i], 5) << endl;
}
return 0;
}
Output
Test case #0 -- max common string at the beginning: abcd
Test case #1 -- max common string at the beginning:
Test case #2 -- max common string at the beginning: a
Test case #3 -- max common string at the beginning:
Given a string list with n strings, calculate the max common string
-- Get an character from string #0
-- Compare it with the char at the corresponding position in all other strings
-- If matched, compare next char, until first mismatch or string terminator occurs
#include <iostream>
using namespace std;
void get_max_comm_str_BFS(char *comm_str, int index, char *strlist[], int n)
{
char c = strlist[0][index];
int i;
if('\0' == c){
comm_str[index] = '\0';
return;
}
for(i = 0; i < n; i++){
if(c != strlist[i][index]){
comm_str[index] = '\0';
return;
}
}
comm_str[index] = c;
get_max_comm_str_BFS(comm_str, index + 1, strlist, n);
}
int main(int argc, char* argv[])
{
char *test_cases[][5] = {
{"abcd","abcdfed","abcdxd","abcdd","abcdpd"}, // should return abc
{"abcd","abcfed","","abcdd","abcpd"}, // should return ""
{"a","a","abcxd","abcdd","abcpd"}, // should return ""
{"xabcd","yabcfed","jabcxd","kabcdd","abcpd"} // should return ""
};
char comm_str[256];
for(int i = 0; i < 4; ++i){
get_max_comm_str_BFS(comm_str, 0, test_cases[i], 5);
cout << "Test case #" << i << " -- max common string at the beginning: " << comm_str << endl;
}
return 0;
}