CareerCup

A finite automaton should work for this, which seems overkill and silly after I wrote the code :-(

2 important states, SPACE and NOTSPACE.

// Assume NULL terminated string.

#define BEGIN 0
#define SPACE 1
#define NOTSPACE 2
#define END 
// Dont really need the END State.

void EmitSequence(char *s, int state) {

    if (s == NULL) {
        state = END;
        return;
    }

    char curChar = *s;

    
    case (state) {
        BEGIN:
            if (curChar == ' ') {
                state = SPACE;
            }
            break;
        SPACE:
            if (curChar == ' ') {
                state = SPACE;
                break;
            }
            // saw a character. Emit a '(' ')'
            putchar('(');
            putchar(curChar);
            putchar(')');

            state = NOTSPACE;
            break:
        NOTSPACE:
            if (curChar == ' ') {
                state = SPACE;
                break;
            }
            // saw a character. Emit a '(' ')'
            putchar('(');
            putchar(curChar);
            putchar(')');
    }
    EmitSequence(s++, state);
}

my $s = shift;  # read in string from the command line
$s =~ s/\s+//g;  # replace all the white spaces in the string with nothing
$s = '(' . $s . ')';  # add the brackets on either side of the string 

print "\n";
print $s; 
print "\n"; 
print $s;

1) Replace all space with ")("
2) Put '(' at begining and ')' at the end

O(n) solution

T: your solution works flawlessly...and its O(n)...You rock buddy!!!

#include <cstdio>
#include <memory>
#include <cstdlib>
#include <cstring>

int main()
{
char arr[] = "a bc defga dcbaifk";

// Allocate enough space if there is space
// if there is space between each of the chars.
int len = strlen(arr)*3 + 1;

char * q, *p , *qstart;
p = arr;

printf(" Start p = %s\n",p);

q = (char *) malloc (sizeof(char) * len);
qstart = q;

*q = '('; q++;

while(p && *p)
{
if(*p == ' ')
{
*q = ')';
q++;
*q = '(';
}
else
{
*q = *p;
}

++q;
++p ;
}

*q = ')';
++q;
*q = '\0';

printf(" End q = %s\n",qstart);
}

host:~/testing$ ./replspc
Start p = a bc defga dcbaifk
End q = (a)(bc)(defga)(dcbaifk)

string Replace(const string& input)
{
   string ret = "";
   bool in_word = false;
   for (int i = 0; i < input.size(); ++i) {
     if (!in_word && input[i] != ' ') {
         in_word = true;
         ret += '(';
         ret += input[i];
     } else if (in_word && input[i] == ' ') {
         ret += ')';
         in_word = false;
     } else if (in_word && input[i] != ' ') {
         ret += input[i];
     }
   }
   if (in_word) {
      ret += ')';
   }
   return ret;
}

}