Hamed Kiani (Ph.D.)
  • Home
  • Publications
  • Contact

A method isSubstring which checks if one word is a substring of another, use this method to check if two strings are rotated.

7/20/2015

3 Comments

 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
/******************************************************************************************
*******************************************************************************************
Chapter 1 Arrays and Strings

 * Assume you have a method isSubstring which checks if one word is a substring of another.
 * Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using
 * only one call to isSubstring (i.e., "waterbottle" is a rotation of "erbottlewat")
 
By: Hamed Kiani (July 20, 2015)
******************************************************************************************
******************************************************************************************/

#include<iostream>
#include<cstring>

using namespace std;

bool is_sub_string(const char* s1, const char* s2)
{
        // check if two strings are not null
        if (!s1 || !s2)
                return false;
        // find the first char of s2, s2[0] in the s1, if found then check the rest of s2 over s1
        int i,j ;
        j = 0;
        for (i = 0; s1[i] != '\0'; i++)
        {
                if (s1[i] == s2[0]) {
                        for(j = 1; s2[j] != '\0'; j++)                    
                                // we are already sure that s1[i] == s2[0]
                                if (s2[j] != s1[i+j])
                                        break;
                }
                // if (s2[j] == '\0') means that we have similar chars till the end of s2
                if (s2[j] == '\0')
                        return true;
        }
        // is not s sub string
        return false;
}

// O(n) time, O(1) additional space.
bool is_rotation_fun1(const char* s1, const char* s2)
{
        if (!s1 || !s2)
                return false;
        if (strlen(s1) != strlen(s2))
                return false;

        while(*s2 != '\0')
                s2++;
        s2--;
        while(*s1 != '\0')
        {
                if (*s1 != *s2)
                        return false;
                s1++; s2--;
        }       
        return true;
}

// O(n) time, O(n) additional space.
// using is_rotation function
// the trick is that we append the inverse of s1 to s1 and then check:
// if is_sub_string(s1+inv(s1[1:length(s1)-1]), s2).
// name + man = nameman
// is is_sub_string(nameman, eman)
bool is_rotation_fun2(  char* s1,   char* s2)
{
        int l1;
        l1 = strlen(s1);            
        char* temp = (char *) malloc( sizeof(char) * l1 * 2);
        char *t1 = s1;   
        int i = 0;
        while(*t1 != '\0')
        {
                temp[i] = *t1;
                t1++; i++;
        }
        // move t1 pointin to end of s1 to next to last char. 
        // accordingly, we change l1 = l1 -2, since we ignore the last char of s1 
        //and consider length counter as [0...strlen(s1)-1]
        t1 -= 2; l1 -= 2;
        while(l1>=0)
        {
                temp[i] = s1[l1];
                l1--; i++;
        }       
        bool check = is_sub_string(temp, s2);
        free(temp);
        return check;
}

void main() {
        char str1[] = "check this string";
        char str2[] = "this";
        bool check ;
        check = is_sub_string(str1,str2);
        cout << check << endl;

        char str3[] = "siht";
        check = is_rotation_fun1(str3, str2);
        cout << check << endl;

        check = is_rotation_fun2(str3, str2);
        cout << check << endl;
}
3 Comments
Gay Party Georgia link
4/4/2021 09:06:03 pm

Great post thankyou

Reply
Curtain Cleaning Weston link
8/23/2022 03:46:35 pm

Appreeciate this blog post

Reply
Cheap Thunder Bay Escorts link
4/10/2025 01:27:47 pm

This code looks very interesting.

Reply



Leave a Reply.

    A place to practice the coding interview.

    Author

    Hamed Kiani

    Categories

    All
    Arrays And Strings
    Linked List
    Stack And Queue
    Trees And Graphs

    Archives

    September 2015
    July 2015

    RSS Feed

Copyright © 2020, Hamed Kiani