[Go] Array and string - Reverse Words in a String

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

 

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

 

Constraints:

• 1 <= s.length <= 104
• s contains English letters (upper-case and lower-case), digits, and spaces ' '.
• There is at least one word in s.

 

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

 

My code

func reverseWords(s string) string {
	buf := []rune(s)
	buf = frontspace(buf)
	buf = backspace(buf)
	buf = removespace(buf)

	l := len(buf)
	reverse(buf, 0, l)
	i := 0
	for j := 0; j < l; j++ {
		if string(buf[j]) == " " {
			reverse(buf, i, j)
			i = j + 1
		}
		if j == l-1 {
			reverse(buf, i, l)
		}

	}
	return string(buf)

}

func reverse(buf []rune, start, end int) {
	for start < end {
		end--
		buf[start], buf[end] = buf[end], buf[start]
		start++
	}

}

func frontspace(buf []rune) []rune {
	l := len(buf)
	temp := make([]rune, 0)
	for i := 0; i < l; i++ {
		if string(buf[i]) != " " {
			buf = append(buf[:0], buf[i:]...)
			break
		}
	}
	temp = buf
	return temp
}

func backspace(buf []rune) []rune {
	l := len(buf)
	temp := make([]rune, 0)
	for i := l - 1; i >= 0; i-- {
		if string(buf[i]) != " " {
			buf = buf[0 : i+1]
			break
		}
	}
	temp = buf
	return temp
}

func removespace(buf []rune) []rune {
	q := 0
	temp := make([]rune, 0)
	for {
		if q > len(buf)-1 {
			temp = buf
			return temp
		}
		if string(buf[q]) == " " && string(buf[q+1]) == " " {
			buf = append(buf[:q], buf[q+1:]...)
			continue
		}
		q++

	}
}

• Because Golang string is immutable, string s will be converted to rune.
• Althought there are built-in functions, I implemented functions which create extra space for handing over values.
• front space will remove when white space will be at front array.
• The principle of this function is that when a space is found, it is overwritten in the array except for the address value where the space is found from the beginning.
• The second function removes the space behind it.
• forloop iterates from the last array to the array with values.
• When a value is found, it overwrites the array from the beginning of the array to the found address.
• Third function will remove Array with two spaces and remove one space.
• After this process, reverse function runs first time from the start to end.
• Last for loop will check space right after string.
• j will be end and i will be j+1.
• first i will be initiaized to 0 for remembering start of each string.
• when j reaches to last array, i and length will be reversed.

sample 0 ms submission

func reverseWords(s string) string {
    
    str := strings.Split(s," ")
    strRet := []string{}
    
    for i, _ := range str{
        if len(strings.TrimSpace(str[i])) != 0{
            strRet = append(strRet, str[i])
        }
    }
   
    for i,j := 0, len(strRet)-1; i<j; i,j = i+1, j-1{
        strRet[i], strRet[j] = strRet[j], strRet[i]
    }
    return strings.Join(strRet," ")
}

sample 1 ms submission

func reverseWords(s string) string {
    words := strings.Split(s, " ")
    stack := []string{}
    for i := range words {
        if words[i] != " " && words[i] != "" {
            stack = append(stack, words[i])    
        }
    }
    
    b := strings.Builder{}
    for len(stack) != 0 {
        wordsLeft := len(stack)
        word := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        b.WriteString(word)
        if wordsLeft != 1 {
            b.WriteString(" ")    
        }
    }
    return b.String()
}

sample 2 ms submission & sample 3100 KB submission

func reverseWords(s string) string {
    words := strings.Fields(s)
    
    for i,j:=0,len(words)-1; i<j; i,j = i+1,j-1 {
        words[i], words[j] = words[j], words[i]
    }
    
    return strings.Join(words, " ")
}

• This code is so simple.
• func Fields(s string) []string: Splits a string with whitespace and saves it as a string slice
• func Join(a []string, sep string) string: concatenates all strings stored in string slice

sample 3 ms submission & sample 2800 KB submission

func reverseWords(s string) string {
    arr := strings.Fields(s)
    
    l, r := 0, len(arr)-1
    for l <= r {
        arr[l], arr[r] = strings.TrimSpace(arr[r]), strings.TrimSpace(arr[l])
        l++
        r--
    }
    
    return strings.Join(arr, " ")
}

sample 4 ms submission

func reverseWords(s string) string {
	strList := strings.Split(s, " ")
	ans := ""
	for i := len(strList)-1; i >= 0; i-- {
		if strList[i] != "" {
			ans += strList[i] + " "
		}
	}
	ans = ans[:len(ans)-1]
	return ans
}

sample 5 ms submission

func reverseWords(s string) string {
    n := strings.Split(s," ")
    l := len(n)
    res := ""
    for i := l-1; i >= 0;i--{
        if n[i] != ""{
            res += n[i]
            res += " "
        }
    }
    res = res[:len(res)-1]
    return res
}

sample 2700 KB submission

func indexOf(s []byte, h byte) int {
	for i, x := range s {
		if x == h {
			return i
		}
	}
	return -1
}

func reverse(s []byte) {
	for i, j := 0, len(s) - 1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

func reverseWords(s string) string {
	sb := []byte(s)
	reverse(sb)
	var next, start, end int
	for ; sb[start] == ' '; start++ {}
	end = start+indexOf(sb[start:], ' ')
	if end <= start {
		end = len(sb)
	}
	for start < len(sb) {
		for i, j := end-1, next; i > j && sb[i] != ' '; i, j = i-1, j+1 {
			sb[j], sb[i] = sb[i], sb[j]
		}
		next += end-start
		for start = end+1; start < len(sb) && sb[start] == ' '; start++ {}
		if start >= len(sb) {
			break
		}
		end = start+indexOf(sb[start:], ' ')
		if end <= start {
			end = len(sb)
		}
		sb[next] = ' '
		next++
	}
	return string(sb[:next])
}

sample 2900 KB submission

func reverseSubStr(s []rune, i,j int) {
    for {
        if i >= j {
            break
        }
        
        s[i], s[j] = s[j], s[i]
        i++
        j--
    }
}

func reverseWords(str string) string {
    length := len(str)
    //fmt.Printf("length = %v\n", length)
    if len(str) == 0 {
        return str
    }
    
    s := []rune(str)
    
    // remove unnecessary spaces
    // step1: remove end trailing spaces
    for {
        if length <= 0 {
            break
        }
        if s[length-1] != ' ' {
            break 
        }
        
        length--
    }
    
    not_start := true
    start := 0
    end := start
    for {
        if end >= length{
            break
        }
        
        if s[end] == ' '{
            if not_start {
                end++
                continue 
            }
            
            if end+1 <= length-1 && s[end+1] == ' ' {
                end++
                continue
            }
        }
        
        not_start = false
        s[start] = s[end]
        end++
        start++
    }
    // new length
    length = start
    //fmt.Printf("start = %v\n", start)
    s = s[:length]
    //fmt.Printf("s = %v\n", string(s))
    
    start = 0
    end = length-1
    
    // reverse whole 
    reverseSubStr(s, start, end) 
    
    start = 0 
    end = start +1
    for {
        if end >=length || start >= length {
            break
        }
        
        if end == length-1 || (end <= length-1 && s[end] == ' ') {
            //fmt.Printf("inloop start = %v end = %v\n", start, end)
            if end == length-1 {
                reverseSubStr(s, start, end) 
            } else {
                reverseSubStr(s, start, end-1) 
            }
            start = end+1
            end = start
            continue
        }
        
        end++
    }
    
    return string(s)
}

sample 3000 KB submission

func reverseWords(s string) string {
    words := make([]string, 0, 0)
    for i := 0; i < len(s); i++ {
        if s[i] == ' ' {
            continue
        }
        j := i
        for j < len(s) && s[j] != ' ' {
            j++
        }
        words = append(words, s[i : j])
        i = j
    }
    return reverse(words)
}

func reverse(words []string) string {
    for l, r := 0, len(words) - 1; l < r; l, r = l + 1, r - 1 {
        words[l], words[r] = words[r], words[l]
    }
    return strings.Join(words, " ")
}

• This looks good concept.
• words string will be created.
• for loop runs until end of array.
• when array has space, for loop will return to start with increased i.
• after this if condition, i value will be handed to j with declaration.
• For loop afte declartion will run until for loop reaches space.
• An address from i to j will be one word and it will be added to words string.
• j value will be handed to i and i will start from next space.
• return will be reverse function result.
• reverse function will exchange lp and rp.
• when l and r meet, for loop will be ended.
• and this function returns after join fucntion with space between words.

 

 

 

 

sample 3200 KB submission

func reverseWords(s string) string {
	// trim leading and trailing whitespaces
	res := strings.TrimSpace(s)
	// split by whitespace
	words := strings.Split(res, " ")
	// drop empty strings in a slice
	i := 0
	for _, word := range words {
		if word != "" {
			words[i] = strings.TrimSpace(word)
			i++
		}
	}
	// shrink
	words = words[:i]
	// reverse
	for i2, j := 0, len(words)-1; i2 < j; i2, j = i2+1, j-1 {
		words[i2], words[j] = words[j], words[i2]
	}
	return strings.Join(words, " ")
}

sample 3300 KB submission

func reverseWords(s string) string {
	words := strings.Split(s, " ")
	p := 0
	//reverse
	for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
		words[i], words[j] = words[j], words[i]
	}

	for i := 0; i < len(words); i++ {
		if words[i] != "" {
			words[p] = words[i]
			p++
		}
	}
	words = words[:p]
	return strings.Join(words, " ")
}