Consider an arbitrary character string of length N. Design an efficient algorith

Question

Consider an arbitrary character string of length N. Design an efficient algorithm that is ON) that determines whether or not the character string is in the form Yz, such that x and z are sequences of X's and Z’s that are mirror images of each other (e.g., x = XZZXZ, z= ZXZZX) and Y is simply the letter Y. Implement the STL find routine that returns the iterator containing the first occurrence of X in the range that begins at start and extends up to, but not including end. If x is not found, end is returned. This is a nonclass (global function) with signature: template typename Iterator, typename objects Iterator find(Iterator start, Iterator end, const object& x)

Explanation / Answer

Please find my answer for Q1.

Please repost other questions in separate post.

Algorithm to check whether a string is in the form xYz

1. S is input string

1. initialize two variables:

i = 1 and j = S.length

3.1 increase i and decrease j until S[i] = S[j]

while i < j and S[i] == S[j]:

i = i + 1

j = j - 1

if( i == j) // Y is not in string, S is on form xz

return TRUE

3.2 from the point where S[i] != S[j], all characters between i to j should be 'Y'

while i < j:

IF S[i] != 'Y' or S[j] != 'Y':

return FALSE

// all characters are 'Y'

return TRUE

Time Compexity:

Since we are traversing all characters only once, so T(n) = O(n)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---