Create a new string that will consist of common letters from other two strings

Question

I'm new to C programming. I have a task to do. User inputs two strings. What I need to do is to create a new string that will consist only from common letters of those two given strings. For example: if given:

str1 = "ABCDZ"
str2 = "ADXYZ"

the new string will look like: "ADZ". I can't make it work. I think there must be a better (more simple) algorithm but I have waisted too much time for this one so I want to complete it .. need your help!

what I've done so far is this:

char* commonChars (char* str1, char* str2)
{
    char *ptr, *qtr, *arr, *tmp, *ch1, *ch2;
    int counter = 1;
    ch1 = str1;
    ch2 = str2;
    arr = (char*) malloc ((strlen(str1)+strlen(str2)+1)*(sizeof(char))); //creating dynamic array
    strcpy(arr, str1);
    strcat(arr,str2);
    for (ptr = arr; ptr < arr + strlen(arr); ptr++)
    {
        for (qtr = arr; qtr < arr + strlen(arr); qtr++) // count for each char how many times is appears
        {
            if (*qtr == *ptr && qtr != ptr)
            {
                counter++;
                tmp = qtr;
            }
        }
        if (counter > 1)
        {
            for (qtr = tmp; *qtr; qtr++) //removing duplicate characters
                *(qtr) = *(qtr+1);
        }
        counter = 1;
    }
    sortArray(arr, strlen(arr)); // sorting the string in alphabetical order
    qtr = arr;
    for (ptr = arr; ptr < arr + strlen(arr); ptr++, ch1++, ch2++) //checking if a letter appears in both strings and if at least one of them doesn't contain this letter -  remove it
    {
        for (qtr = ptr; *qtr; qtr++)
        {
            if (*qtr != *ch1 || *qtr != *ch2)
                *qtr = *(qtr+1);
        }
    }
}

Don't know how to finish this code .. i would be thankful for any suggestion!

Answer 1

The output array cannot be longer that the shorter of the two input arrays. You can use strchr().

char * common (const char *in1, const char *in2) {
    char *out;
    char *p;

    if (strlen(in2) < strlen(in1)) {
        const char *t = in2;
        in2 = in1;
        in1 = t;
    }

    out = malloc(strlen(in2)+1);
    p = out;
    while (*in1) {
        if (strchr(in2, *in1)) *p++ = *in1;
        ++in1;
    }
    *p = '\0';
    return out;
}

This has O(NxM) performance, where N and M are the lengths of the input strings. Because your input is alphabetical and unique, you can achieve O(N+M) worst case performance. You apply something that resembles a merge loop.

char * common_linear (const char *in1, const char *in2) {
    char *out;
    char *p;

    if (strlen(in2) < strlen(in1)) {
        const char *t = in2;
        in2 = in1;
        in1 = t;
    }

    out = malloc(strlen(in2)+1);
    p = out;
    while (*in1 && *in2) {
        if (*in1 < *in2) {
            ++in1;
            continue;
        }
        if (*in2 < *in1) {
            ++in2;
            continue;
        }
        *p++ = *in1;
        ++in1;
        ++in2;
    }
    *p = '\0';
    return out;
}

Answer 2

I will do something like this :

char*   commonChars(char* str1, char* str2) {
   char*  ret = malloc(strlen(str1) * sizeof(char));
   int    i = j = k = 0;

   for (; str1[i] != '\n'; i++, j++) {
       if (str1[i] == str2[j]) {
          ret[k] = str1[i];
          k++;
       }
    }
  ret[k] = '\0';
  ret = realloc(ret, k);
  return ret;
}

It's been a while i didn't do C, hope this is correct

Answer 3

Sorry for the weird use of char arrays, was just trying to get it done fast. The idea behind the algorithm should be obvious, you can modify some of the types, loop ending conditions, remove the C++ elements, etc for your purposes. It's the idea behind the code that's important.

#include <queue>
#include <string>
#include <iostream>
using namespace std;


bool isCharPresent(char* str, char c) {
    do {
        if(c == *str) return true;
    } while(*(str++));

    return false;
}

int main ()
{
    char str1[] = {'h', 'i', 't', 'h', 'e', 'r', 'e', '\0'};
    char str2[] = {'a', 'h', 'i', '\0'};
    string result = "";

    char* charIt = &str1[0];

    do {
        if(isCharPresent(str2, *charIt))
            result += *charIt;
    } while(*(charIt++));


    cout << result << endl; //hih is the result.  Minor modifications if dupes are bad.
}

Answer 4

You can use strpbrk() function, to do this job cleanly.

const char * strpbrk ( const char * str1, const char * str2 );
char * strpbrk (       char * str1, const char * str2 );

Locate characters in string Returns a pointer to the first occurrence in str1 of any of the characters that are part of str2, or a null pointer if there are no matches.

The search does not include the terminating null-characters of either strings, but ends there.

#include <stdio.h>
#include <string.h>

int main ()
{
  char str[] = "ABCDZ";
  char key[] = "ADXYZ";

  char *newString = malloc(sizeof(str)+sizeof(key));
  memset(newString, 0x00, sizeof(newString));

  char * pch;
  pch = strpbrk (str, key);

  int i=0;
  while (pch != NULL)
  {
     *(newString+i) = *pch;
     pch = strpbrk (pch+1,key);
     i++;
  }

  printf ("%s", newString);
  return 0;
}

Answer 5

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define min(x,y) ((x)<(y)? (x) : (y))

char* commonChars (const char *str1, const char *str2){
    //str1, str2 : sorted(asc) and unique
    char *ret, *p;
    int len1, len2;
    len1=strlen(str1);
    len2=strlen(str2);
    ret = p = malloc((min(len1, len2)+1)*sizeof(char));

    while(*str1 && *str2){
        if(*str1 < *str2){
            ++str1;
            continue;
        }
        if(*str1 > *str2){
            ++str2;
            continue;
        }
        *p++ = *str1++;
        ++str2;
    }
    *p ='\0';

    return ret;
}

char *deleteChars(const char *str, const char *dellist){
    //str, dellist : sorted(asc) and unique
    char *ret, *p;
    ret = p = malloc((strlen(str)+1)*sizeof(char));

    while(*str && *dellist){
        if(*str < *dellist){
            *p++=*str++;
            continue;
        }
        if(*str > *dellist){
            ++dellist;
            continue;
        }
        ++str;
        ++dellist;
    }
    if(!*dellist)
        while(*str)
            *p++=*str++;
    *p ='\0';

    return ret;
}

int main(void){
    const char *str1 = "ABCDXYZ";
    const char *str2 = "ABCDZ";
    const char *str3 = "ADXYZ";
    char *common2and3;
    char *withoutcommon;

    common2and3 = commonChars(str2, str3);
    //printf("%s\n", common2and3);//ADZ
    withoutcommon = deleteChars(str1, common2and3);
    printf("%s\n", withoutcommon);//BCXY

    free(common2and3);
    free(withoutcommon);
    return 0;
}

Answer 6

So i found the solution for my problem. Eventually I used another algorithm which, as turned out, is very similar to what @BLUEPIXY and @user315052 have suggested. Thanks everyone who tried to help! Very nice and useful web source!

Here is my code. Someone who'll find it useful can use it. Note: (1) str1 & str2 should be sorted alphabetically; (2) each character should appear only once in each given strings;

char* commonChars (char* str1, char* str2)
{
    char *ptr, *arr,*ch1, *ch2;
    int counter = 0;
    for (ch1 = str1; *ch1; ch1++)
    {
        for(ch2 = str2; *ch2; ch2++)
        {
            if (*ch1 == *ch2)
                counter++;
        }
    }
    arr =  (char*)malloc ((counter+1) * sizeof(char));
    ch1 = str1;
    ch2 = str2;
    ptr = arr;
    for (ch1 = str1; *ch1; ch1++,ch2++)
    {
    while (*ch1 < *ch2)
    {
        ch1++;
    }
    while (*ch1 > *ch2)
    {
        ch2++;
    }
    if (*ch1 == *ch2)
    {
        *ptr = *ch1;
        ptr++;
    }
    }
    if (ptr = arr + counter)
        *ptr = '\0';
    return arr;

}