0

trying to write function that returns 1 if every letter in “word” appears in “s”. for example: 

containsLetters1("this_is_a_long_string","gas") returns 1

containsLetters1("this_is_a_longstring","gaz") returns 0

containsLetters1("hello","p") returns 0

Can't understand why its not right:

#include <stdio.h> 
#include <string.h>
#define MAX_STRING 100

int containsLetters1(char *s, char *word)
{
int j,i, flag;
long len;
len=strlen(word);

for (i=0; i<=len; i++) {
    flag=0;
    for (j=0; j<MAX_STRING; j++) {
        if (word==s) {
            flag=1;
            word++;
            s++;
            break;
        }
        s++;
        
    }
    if (flag==0) {
        break;
    }
}
return flag;
}

int main() {
    char string1[MAX_STRING] , string2[MAX_STRING] ;

printf("Enter 2 strings for containsLetters1\n");

scanf ("%s %s", string1, string2);

printf("Return value from containsLetters1 is: %d\n",containsLetters1(string1,string2));

 return 0; 
4
  • your scanf call is unsafe - i can enter string longer that 100 chars and smash your stack Commented Jan 8, 2014 at 19:30
  • The inner loop should be over the valid length of s, rather than MAX_STRING. You also lose the original values of s (and word), so you can't start at the beginning again to match the second character in word. Commented Jan 8, 2014 at 19:31
  • You are comparing pointers, not the values they are pointing to to start. There is a whole lot more wrong with not correctly verifying string lengths, resetting pointers backward when a mismatch is encountered, etc Commented Jan 8, 2014 at 21:30
  • Your code actually works on characters, not "letters". Nowhere in the code is there any restriction to letters. For instance if the word is sugar-free, and the string has all those letters, but does not have a hyphen, it fails. Your code also neglects case. Even if the left string has all the lower case letters of the alphabet, like the quick brown fox jumped over the lazy dogs, but the word contains upper case letters, then the code also fails. If by "letter" you mean "any character other than null, printable or not", you should fix the problem specification. Commented Jan 8, 2014 at 21:53

5 Answers 5

2

Try these:

  1. for (i=0; i < len; i++)... (use < instead of <=, since otherwise you would take one additional character);
  2. if (word==s) should be if (*word==*s) (you compare characters stored at the pointed locations, not pointers);
  3. Pointer s advances, but it should get back to the start of the word s, after reaching its end, i.e. s -= len after the for (j=...);
  4. s++ after word++ is not needed, you advance the pointer by the same amount, whether or not you found a match;
  5. flag should be initialized with 1 when declared.
Sign up to request clarification or add additional context in comments.

Comments

2

Ah, that should be if(*word == *s) you need to use the indirection operator. Also as hackss said, the flag = 0; must be outside the first for() loop.

1 Comment

It didn't fix the problem
1

Unrelated but probably replace scanf with fgets or use scanf with length specifier For example

 scanf("%99s",string1)

Things I can see wrong at first glance:

  1. Your loop goes over MAX_STRING, it only needs to go over the length of s.
  2. Your iteration should cover only the length of the string, but indexes start at 0 and not 1. for (i=0; i<=len; i++) is not correct.
  3. You should also compare the contents of the pointer and not the pointers themselves. if(*word == *s)
  4. The pointer advance logic is incorrect. Maybe treating the pointer as an array could simplify your logic.

Another unrelated point: A different algorithm is to hash the characters of string1 to a map, then check each character of the string2 and see if it is present in the map. If all characters are present then return 1 and when you encounter the first one that is not present then return 0. If you are only limited to using ASCII characters a hashing function is very easy. The longer your ASCII strings are the better the performance of the second approach.

Comments

1

Here is a one-liner solution, in keeping with Henry Spencer's Commandment 7 for C Programmers.

#include <string.h>

/*
 * Does l contain every character that appears in r?
 *
 * Note degenerate cases: true if r is an empty string, even if l is empty.
 */

int contains(const char *l, const char *r)
{
  return strspn(r, l) == strlen(r);
}

However, the problem statement is not about characters, but about letters. To solve the problem as literally given in the question, we must remove non-letters from the right string. For instance if r is the word error-prone, and l does not contain a hyphen, then the function returns 0, even if l contains every letter in r.

If we are allowed to modify the string r in place, then what we can do is replace every non-letter in the string with one of the letters that it does contain. (If it contains no letters, then we can just turn it into an empty string.)

void nuke_non_letters(char *r)
{
  static const char *alpha =
    "abcdefghijklmnopqrstuvwxyz"
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

  while (*r) {
    size_t letter_span = strspn(r, alpha);
    size_t non_letter_span = strcspn(r + letter_span, alpha);
    char replace = (letter_span != 0) ? *r : 0;
    memset(r + letter_span, replace, non_letter_span);
    r += letter_span + non_letter_span;
  }
}

This also brings up another flaw: letters can be upper and lower case. If the right string is A, and the left one contains only a lower-case a, then we have failure.

One way to fix it is to filter the characters of both strings through tolower or toupper.

A third problem is that a letter is more than just the 26 letters of the English alphabet. A modern program should work with wide characters and recognize all Unicode letters as such so that it works in any language.

By the time we deal with all that, we may well surpass the length of some of the other answers.

1 Comment

+1 — I looked at strcspn() and didn't come up with a solution after all, but I didn't spot the strspn() on the reversed arguments. Well done. Very neat.
0

Extending the idea in Rajiv's answer, you might build the character map incrementally, as in containsLetters2() below.

The containsLetters1() function is a simple brute force implementation using the standard string functions. If there are N characters in the string (haystack) and M in the word (needle), it has a worst-case performance of O(N*M) when the characters of the word being looked for only appear at the very end of the searched string. The strchr(needle, needle[i]) >= &needle[i] test is an optimization if there are likely to be repeated characters in the needle; if there won't be any repeats, it is a pessimization (but it can be removed and the code still works fine).

The containsLetters2() function searches through the string (haystack) at most once and searches through the word (needle) at most once, for a worst case performance of O(N+M).

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

static int containsLetters1(char const *haystack, char const *needle)
{
    for (int i = 0; needle[i] != '\0'; i++)
    {
        if (strchr(needle, needle[i]) >= &needle[i] &&
            strchr(haystack, needle[i]) == 0)
            return 0;
    }
    return 1;
}

static int containsLetters2(char const *haystack, char const *needle)
{
    char map[256] = { 0 };
    size_t j = 0;

    for (int i = 0; needle[i] != '\0'; i++)
    {
        unsigned char c_needle = needle[i];
        if (map[c_needle] == 0)
        {
            /* We don't know whether needle[i] is in the haystack yet */
            unsigned char c_stack;
            do
            {
                c_stack = haystack[j++];
                if (c_stack == 0)
                    return 0;
                map[c_stack] = 1;
            } while (c_stack != c_needle);
        }
    }
    return 1;
}

int main(void)
{
    assert(containsLetters1("this_is_a_long_string","gagahats") == 1);
    assert(containsLetters1("this_is_a_longstring","gaz") == 0);
    assert(containsLetters1("hello","p")  == 0);

    assert(containsLetters2("this_is_a_long_string","gagahats") == 1);
    assert(containsLetters2("this_is_a_longstring","gaz") == 0);
    assert(containsLetters2("hello","p")  == 0);
}

Since you can see the entire scope of the testing, this is not anything like thoroughly tested, but I believe it should work fine, regardless of how many repeats there are in the needle.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.