String Problems involving 2 strings

1. Strings are rotations of each other or not
Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 using only one call to strstr routine?
(eg given s1 = ABCD and s2 = CDAB, return true, given s1 = ABCD, and s2 = ACBD , return false)
Method 1:
http://www.geeksforgeeks.org/a-program-to-check-if-strings-are-rotations-of-each-other-or-not/

The first thing, of course, would be to make sure that both the strings have same length. Now, suppose these strings are str1 and str2 and one of them is a rotation of the other(eq. str1 = "google" and str2 = "oglego"). Append str2 to itself(making "oglegooglego"). Now, if we have a function to find a substring within a string, we can use it to find str1 in modified str2. If found, then str2 is a rotation of str1.

Code:
boolean checkRotation(string s1, string s2)
  if( len(s1) != len(s2))
    return false
  if( substring(s2,concat(s1,s1))
    return true
  return false
end
Method 2:
However if this doesn't clicks to the person's mind, then we can use modulo operator method. Let s1 = char[] a, and s2 = char b[]. Find index of b[0] in a. You may get single index  called IN or no index or multiple  index. In case of no index, you can simply return false. In case of single index, you can check if a[IN+1] = b[1] and so on. If at any point mismatch happens, you can simply return the value. In case of multiple index, same procedure is repeated as for single index, but for multiple time.

2. Implement strstr()
http://www.programcreek.com/2012/12/leetcode-implement-strstr-java/

Code:

char* strstr(const char* str, const char* pattern)

{

      if(!*pattern)

        return (char*)str;

      char* ptr1=(char*)str;

      char* ptr2=(char*)pattern;

      int len=0;

      while(*ptr2!='\0')  //  or (*ptr2!='\0')

      {

         len++;

         ptr2++;

      }

      ptr2=(char*)pattern;

      while(*(ptr1+len-1))   

//actual offset for the end of the pattern

      {

         int i;

         for(i=0;i < len;i++)

         {

            if(*(ptr1+i)!=*(ptr2+i))

              break;

         }

         if(i==len)

           return ptr1;

         else

           ptr1++;

      }

      return NULL;

}

Do not forget to take care of the base case where the pattern sent is NULL, in this case we return the starting of the string as the answer.

Since we are calculating the length of the pattern in the beginning we need not go till the end of the string. We will have to compare only till N-M+1 if N is the length of the string and M is the length of the pattern. So the complexity is O((M-N+1)*N)

4. Isomorphic Strings
http://www.programcreek.com/2014/05/leetcode-isomorphic-strings-java/

5. Anagrams
http://www.programcreek.com/2014/05/leetcode-valid-anagram-java/

6. All interleaving of two Strings
http://www.geeksforgeeks.org/print-all-interleavings-of-given-two-strings/

7. Scramble String
http://www.programcreek.com/2014/05/leetcode-scramble-string-java/

8. String are One Edit Distance Apart or not
http://www.programcreek.com/2014/05/leetcode-one-edit-distance-java/

9.Return the index of the 1st character in str1 that matches any character in str2
Most efficient way to return the index of the 1st character in str1 that matches any character in str2
Given a function int strcspn(string find, string src) code the most efficient way  to return the index of the 1st character in "src" that matches any character in "find".

Method 1: Hash Map
Build a hash look up table of all chars in src string. Then scan find string and return index of first char that exists in look up table.

- Add every char from src to unordered_hashmap with the char as key and no of times it occurs in the src string as value
- hence, src will be transformed as (g,2) (a,2) and (b,2) in the map.
- now check if every char from "find" string is is present in the map.
- if any char is found, find the index of that char in the "find" string and thats it !
- fetching from map is O(1)
- looking up every char from "find" takes O(n) where n=strlen(find)
- additional space of O(n) for the map !

Method 2: Integer Bits
The fastest is: as there are less than 32 character types (let's suppose it is not Unicode) you can represent the search values in an integer: go through the find array and OR it's shifted values to the integer, marking the bit 1 if it's a searchable char (a> 0001 b>0010 ...)

Then start processing the the input, AND ing all shifted values to this array. If the result is greater than 0 that is your first match.

Please note that even though hashtable is considered to be O(1) no interviewer will accept the answer for a fixed size input as optimal ;)

https://www.careercup.com/question?id=12651662

10. Concatenate two strings
Concatenate two strings omitting the overlapping string.e.g
If str1=hello everyone and str2=everyone is good then answer should be
hello everyone is good

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

char *Strcat(char *dst, const char *src)
{
        size_t dstLen = strlen(dst);
        size_t srcLen = strlen(src);


        char *p  = dst + dstLen + srcLen;  /* Pointer to the end of the concatenated string */

        const char *q  = src + srcLen - 1; /* Pointer to the last character of the src */

        char *r  = dst + dstLen - 1;      /* Temp Pointer to the last character of the dst*/

        char *end = r;                  /* Permenent Pointer to the last character of the dst*/

        *p = '\0';  /*terminating the concatened string with NULL character */


        while(q >= src)   /*Copy src in reverse*/
        {
                if(*r == *q) /*Till it matches with the src, decrement r */
                {
                        r--;
                }
        
                else

                {
                        r = end;

                        if(*r == *q)

                        {

                          r--;
                        }
                }

                *p-- = *q--;
        }

        while(r >= dst) /*Copy dst, ending with r */
                *p-- = *r--;

        return p + 1;
}

int main()
{
        char a[64] = "hello everyone";
        const char *b  = "everyone is good";

        printf("%s\n", Strcat(a, b));

        getchar();
        return 0;
}