You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to compute all possible states of the string after one valid move.
http://www.programcreek.com/2014/04/leetcode-flip-game-java/
Write a function to compute all possible states of the string after one valid move.
http://www.programcreek.com/2014/04/leetcode-flip-game-java/
Shouldn't the complexity be O((N-M+1)*M)
ReplyDeleteHey Sumit,
ReplyDeleteyou can think it this way.Lets say the the pattern is of only 1 character.Then we need to travel the whole string.So it should be O(N-M+1)*N only.And O(N-M+1)*N and O(M-N+1)*N are same as we take a mode of M-N+1
Hi Sudhansu,
ReplyDeleteI did not understand why we are using while(*(ptr1+len-1))
Its enough to use while(*str) right?
I suspect that you are trying way to hard.
ReplyDeleteThe following is much shorter, simpler, and easier to convince of correctness.
char *strstr(const char *s1, const char *s2) {
const char *a = s1, *b = s2;
for (;;) {
if (!*b) return (char *)a;
if (!*a) return NULL;
if (*a++ == *b++) continue;
a = ++s1;
b = s2;
}
}