Given a string with spaces, normalize it.


  • 0
    B

    Got asked this by Google (coderpad screen) a few years ago. Given a string with spaces, normalize it.

    Input: "  Hello My    World    P  "
    Output: "Hello My World P"
    

    I don't remember if this involved just spaces or any white space (tabs, carriage return). If someone else has encountered this question, please clarify.


  • 0

    Think this will solve it.

    	public String normalizeString(String source) {
    		if (source == null || source.isEmpty()) {
    			return source;
    		}
    		StringBuilder sb = new StringBuilder();
    		int readPtr = 0;
    		// Keep track if we've seen a space as one space is legal.
    		boolean seenSpace = false;
    		// Disregard leading spaces.
    		while (source.charAt(readPtr) ==  ' ') {
    			readPtr++;
    		}
    		for (; readPtr < source.length(); readPtr++) {
    			char c = source.charAt(readPtr);
    			if (c == ' ' && seenSpace) {
    				while (source.charAt(readPtr) ==  ' ') {
    					readPtr++;
    				}
    			} else {
    				if (c == ' ') {
    					seenSpace = true;
    				} else {
                                            seenSpace = false;
                                    }
    				sb.append(c);
    			}
    		}
    		return sb.toString();
    	}
    

  • 3
    S

    Why not use simple regEx? Was there any condition of not use the regex:

    '''

        String s = "Hello    World and    aloha";
        String s1 = s.replaceAll("\\s+", " ");
        System.out.println(s1);
    

    '''


  • 0
    B

    @sunils I do not recall such a condition. So yeah that seems like a good way to do it if you know exact regex to use. While I know the concept of regex I would need to lookup which one to use.


  • 0
    B

    @sunils I was doing some testing and I realize that your solution will not work for the string

    "    Hello    World and    aloha"
    

    One workaround might be to trim() the string before or after.


  • 0
    S

    If it has to be done in-place that would involve calculating the start, end of the original string that has normalized part of the string.
    The below impl may not be fully robust but it goes like this (Java):

    char[] c = s.toCharArray();
    int start = -1;
    for ( int i = 0; i < c.length; i++ ) {
       int temp = i;
       while( i < c.length && Character.isWhiteSpace(c[i]) ) i++;
       if ( start == -1 ) start = i;
       if ( i != temp ) {
         
         temp = temp + 1;
         int grab = i - temp;
         while ( temp < c.length && grab >= 0 ) {
             c[temp] = c[i];
             c[i] = ' ';
             temp++;
             grab--;
         }
         end = temp;
      }
     }
    
    return String.valueOf ( Arrays.copyOf( c, start, end ) );

  • 0
    S

    This should cover all the escape characters.

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define true 1
    #define false 0
    
    int normalize(char* input);
    
    int main(){
        //char input[] = "  Hello My    World    P  ";
        char input[] = "    Hello    World and    aloha";
        printf("Input: [%s]\n", input);
        int rc = normalize(input);
        if(rc == 0){
            printf("Output: [%s]\n", input);
        }
        return rc;
    }
    
    int isEscapeChar(char a){
        switch(a){
            case ' ':
            return true;
            case '\t':
            return true;
            case '\r':
            return true;
        }
        return false;
    }
    
    int normalize(char *input){
        int len = strlen(input); //assuming it is null terminated;
        char* normStr = (char*)malloc(sizeof(char)*len);
        if(normStr == NULL){
            printf("Malloc Failed");
            return -1;
         }
    
         int expectChar = true;
         int normStrPos=0;
         for(int i = 0 ; i<len; i++){
             if(expectChar && (isEscapeChar(input[i]))){
                 continue;
             }else if(isEscapeChar(input[i])){
                 normStr[normStrPos++]=' ';
                 expectChar=true;
             }else{
                 normStr[normStrPos++]=input[i];
                 expectChar=false;
             }
         }
         if(isEscapeChar(normStr[normStrPos-1])){
             normStrPos--;
         }
         normStr[normStrPos]='\0';
         strlcpy(input,normStr,normStrPos+1);
         free(normStr);
         return 0;
    }
    

  • 0
    S
    string cut(string trun){
        for(int i = 0; i < trun.length()-1;){
            if(isspace(trun[i]) && isspace(trun[i+1])){
                trun.erase(i,1);
            }else if(i == 0 && isspace(trun[i])){
                trun.erase(i,1);
            }
            else{
                i++;
            }
    
        }
        if(trun[trun.length()-1] == ' '){
            trun.erase(trun.length()-1,1);
        }
        return trun;
    }
    

  • 0
    S
    This post is deleted!

  • 0
    C

    @bamashah said in Given a string with spaces, normalize it.:

    " Hello My World P

    string = " Hello My World P "
    string.split(" ").filter(word=> word!=="").join(" ")


  • 1
    K

    Simple python method:

    def normalizeString(arg):
        s=arg.split()
        s1=" ".join(s)
        return s1
    
    print(normalizeString(" Hello        world      p    "))
    

    this method can normalize any given string


  • 0
    C

    " ".join(" Hello My World P ".split())


  • 0
    P

    similar to @Scarecrow_SN solution but using python's pop instead of erase

    def normalizeString(s):
      listStr = list(s) # Convert to string for modifying list
      ind = 0
      while ind < len(listStr) - 1:
        if listStr[ind] == listStr[ind+1] and listStr[ind] == ' ':
          listStr.pop(ind+1)
        else:
          ind += 1
    
      # Check if first and last have spaces, if so remove them
      if listStr[0] == ' ':
        listStr.pop(0)
      if listStr[-1] == ' ':
        listStr.pop(-1)
      return ''.join(listStr)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.