CareerCup

whitespacecount=0;
string= given string;
Step1: Iterate thro the string by each and every character.
If( string[i]==' ')
{
If (IsNotSplCharacter(string[i-1]))
whitespacecount++;
}
else
string[i-whitespacecount]= string[i];
Complexity is O(n).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STRING 100
#define NEW_LINE1 printf("\n");
#define NEW_LINE2 printf("\n\n");
#define STR_LEN(x) printf("\n\nstrlen == %d", strlen(x));

void remove_whitespace(char *str1);

int main(int argc, char *argv[])
{

char *str1 = calloc(1, MAX_STRING);
char *str2 = calloc(1, MAX_STRING);

str1 = " abcd efgh ijkl mnop ";

remove_whitespace(str1);
system("PAUSE");
return 0;
}

void remove_whitespace(char *str1)
{
char *str1_local = calloc(1, MAX_STRING);
char *str2_local = calloc(1, MAX_STRING);
char *str2_final = calloc(1, MAX_STRING);
int i = 0;
strcpy(str1_local, str1);
int length = 0;

printf("\nstr1_local = %d, %s", str1_local, str1_local);
printf("\nstr2_local = %d, %s", str2_local, str2_local);
printf("\nstr2_final = %d, %s", str2_final, str2_final);
NEW_LINE2;
NEW_LINE2;

do {
str2_local = strchr(str1_local, 32);

if(str2_local) {
NEW_LINE1;
strncat(str2_final , str1_local, str2_local - str1_local);
printf("\nstr1_local = %d, %s", str1_local, str1_local);
printf("\nstr2_local = %d, %s", str2_local, str2_local);
printf("\nstr2_final = %d, %s", str2_final, str2_final);
NEW_LINE1;
str1_local = str2_local + 1;
}
else {
strncat(str2_final , str1_local, strlen(str1_local));
}
length++;

} while (str2_local);

NEW_LINE2;
puts(str2_final);
STR_LEN(str2_final);
NEW_LINE2;

free (str1_local);
free (str2_local);
free (str2_final);
}

Is it necessary to do it in place? Why not read the whole string char by char and output to new variable if its non extra whitespace or valid character. O(n)

One way of solving is given below :

- for every character in the string, check if it is a redundant space
- If it is, then keep a count of the redundant spaces encountered so far and shift the position of the current character left by "count" times

pseudo code :


function adjust_spaces(char s[])
{

redundant_spaces_count = 0;
for(int i=0;i<s.length();i++)
{
if(redundant_space(s[i]))
redundant_spaces_deleted++;
else
s[i-redundant_spaces_deleted] = s[i];
}
}

How about using a linked list with O(n)

Node result = new Node(); Node before = null;
for (Node character = start; character != null; character = character.next)
{
if (character.data == ' ' && before == null)
{
before = character.next; result = character.next;
}
else if (character.data == ' ')
{
before.next = character.next;
}
else
before = character;
}

here it is in c# using Regex

{
Console.Write(Regex.Replace(" test man , this is not ! Where to go lamp ",@"\s+", " ").Trim())
}

void Replaces(char* str)
{
	int it =0;
	int in=0;
	bool iswhite = false;
	while( str[it] != '\0')
	{
		if( str[it] == ' ' )
			it++;
		else
			break;
	}
	while( str[it] != '\0')
	{
		if(( iswhite) && (str[it] == ' '))
		{
			it++;
		}
		else
		{
			str[in] = str[it];
			if( str[it] == ' ')
				iswhite = true;
			else
				iswhite = false;
			it++;
			in++;
		}
	}
	if( iswhite)
		str[--in] = '\0';
	else
		str[in] = '\0';
}

What's the time complexity time of my code?

public class RemoveWhiteSpace {

	public static void removeSpace(char[] string) {
		int spacePtr = 0;
		while(spacePtr < string.length && string[spacePtr] != ' '){
			spacePtr++;
		}
		int index = 0;
		for(index = spacePtr;index < string.length; index++){
			if(string[index] == ' '){
				continue;
			}else{
				swap(string,spacePtr,index);
				while(spacePtr < string.length && string[spacePtr] != ' '){
					spacePtr++;
				}
			}
		}
		while(spacePtr < string.length){
			string[spacePtr] = 0;
			spacePtr++;
		}
		for(char c:string){
			System.out.print(c);
		}
		System.out.println();
	}

	private static void swap(char[] string, int spacePtr, int index) {
		char tmp = string[spacePtr];
		string[spacePtr] = string[index];
		string[index] = tmp;
	}

	public static void main(String[] args) {
		removeSpace(" ab  bc d".toCharArray());
		removeSpace("ab ed d d".toCharArray());
	}

}

trim()

I think you can also use str.replaceAll(" "," ") // replace all double spaces with one space. Check if it starts or ends with a space , and delete it, if so.

use
String str2=str.trim() -to remove leading and trailling white spaces
now
String str3=str2.replaceAll("\\s+"," ")

in above reply to the question
replaceAll replaces uneven number of white spaces with single white space
in order to remove them completely use replaceAll("\\s+","")