Strings : String To See If It Contains Palindromes

0
1026

PalinDromes in a String at HiringLibrary-Com

Check a given string to see if it contains palindromes.

Rationale : We will assume the given string is in fact a sentence of words, separated by a single or multiple space characters. In this case, we can use a standard function such as strtok() in order to split the given sentence into words, using the delimiter “ “. A word is a palindrome if it is equal to its reversed form.

For example, given “this is aba a sample string”, we split it into words and check whether the word is a palindrome. For example, “this” and “siht” are not equal, but “aba” and “aba” are, which means “aba” is a palindrome.


 

Before solving this problem do the following (not limited to):

  • Clarify doubts
  • Write/loudly speak/analyze single or multiple pseudocode(e.g. trivial algorithm to advanced algorithm/Data Structures) which can lead to solution
  • Explain any assumptions or limitations on the written pseudocode
  • Mention major data structures to be used
  • Also how the positive/negative functional tests prove that the resultant solution is correct. 

Professional Teacher at HiringLibrary.com

Clarification Points 

 

Clarification Point-1:

Is the given string a word or a sentence containing multiple words?

Clarification Point-2:

How will the words be separated? What kind of characters does the string contain?

Clarification Point-3:

What is the maximum size of the given string?

Diversity in WorkPlace - Japanese,Korea,Chinese

Pseudo Code

Pseudo code:

Contains_palindromes(s)
  Split s into words, separated by “ “
  For each word
    Reverse word
    If initial word = reversed word
      Return true
  Return false;

 

How did you find your first job?

Assumptions/Limitations

Assumption/Limitation:

  • We will assume our string contains at most 200 characters.
  • We will also assume it only contains letters of the English alphabets and spaces, while spaces separate the words

Career Summary from a Professional for HiringLibrar

Major Data Structures 

Major data structures:

Array of characters (string)

.

Example at Hiring Library

Unit tests:  
Postive Functional Test cases  
Input Expected Output
S = “I am here”

S = “test string”

S = “test aba”

S = “ “

S = “abcabc abccba ab”

No palindromes

No palindromes

The string contains palindromes

No palindromes

The string contains palindromes

Negative Functional Test Cases
String contains other characters than “ “ and letters Invalid input!

Answer of the coding Problem

Here is the sample answer that implements the solution described above

#include <cstdio>
#include <string.h>

using namespace std;

bool contains_palindromes(char s[])
{
  for (int stringIndex = 0; stringIndex < strlen(s); stringIndex++)
    if (s[stringIndex] != ' ' && !(s[stringIndex] >= 'a' && s[stringIndex] <= 'z')
        && !(s[stringIndex] >= 'A' && s[stringIndex] <= 'Z'))
    {
      printf("Invalid input!\n");
      return false;
    }

  // split the string into words using strtok
  char *word = strtok(s, " ");
  char word_reversed[200];

  while(word)
  {
    // reverse current word and store it
    strrev(word);
    strcpy(word_reversed, word);
    // bring initial word back to its initial form
    strrev(word);

    // if current word == its reversed form then it's a palindrome
    if (!strcmp(word, word_reversed))
      return true;
    word = strtok(NULL, " ");
  }

  return false;
}

int main()
{
  char s[200];
  strcpy(s, "this is aba a sample string");

  if (contains_palindromes(s))
    printf("The string contains palindromes!");
  else
    printf("The string does not contain palindromes!");
  return 0;
}

Output at HiringLibrary-Com

Output and Further Excercise

Further Exercise at HiringLibrary

Output: Further exercise:
this is aba a sample string

The string contains palindromes!

 

Q: Can you extend the problems to handle more than just words?

A: Yes, string reversal works for any character.

Q: What if the sentences contained punctuation marks?

A: We would need to use multiple separators for the strtok function.