Leetcode - 557. Reverse Words in a String III

문제

다음과 같이 space로 구분된 문자열을 각각 reverse시켜라.

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

https://leetcode.com/problems/reverse-words-in-a-string-iii/

풀이 c++

class Solution {
public:
    string reverseWords(string s) {
        int st = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ' ') {
                reverse(s.begin() + st, s.begin() + i);
                st = i + 1;
            }
        }
        reverse(s.begin() + st, s.end());   
        return s;
    }
};

[참고] 다음은 일반 문자열을 재귀적으로 reverse 하는 함수. (이 문제의 해답 아님)

    string reverseStr(string s) {
        if (s.empty())
            return "";
        return reverseStr(s.substr(1,s.length())) + s.substr(0,1);
    }

풀이 Scala

FP스타일로 해결

object Solution {
    def reverseWords(s: String): String = {
        s.split(" ").map(x => x.reverse).mkString(" ")
    }
}

흥미로운점은 같은 FP스타일의 코드인데 Scala 버전은 (runtime 558 ms, memory 55.5 MB)가 소비되었고, Rust버전은 (runtime 3 ms, memory 2.4 MB)가 소비되었다.

scala에서 split/map/mkString 함수를 coposition하면서 시간복잡도가 n -> 3n 으로 증가해서 그렇지 않았을까 싶다. 반면 Rust는 Zero Cost Abstraction원칙에 따라 컴파일러가 최적화를 해주어서 속도와 메모리측면에서 개선이 되었을것같다. 참고로 C++ 버전은 (runtime 10 ms, memory 9.8 MB)

풀이 Rust

FP스타일로 해결

impl Solution {
    pub fn reverse_words(s: String) -> String {
        s.split(" ")
            .map(|x| x.chars().rev().collect::<String>())
            .collect::<Vec<String>>()
            .join(" ")
    }
}

아래는 해설.

// https://rinthel.github.io/rust-lang-book-ko/ch13-02-iterators.html     
    
fn reverse_str(s: String) -> String {    
    s.split(' ')    
        .map(|x| x.chars().rev().collect::<String>())    
    //             ^^^^^^^       ^^^^^^^ iterator works after consumer     
    //             making to iterator     
        .collect::<Vec<String>>()    
    //   ^^^^^^^  ^^^^^^^^^^^^^     
    //     |       specify what type of iterator     
    //     because map() returns an iterator     
        .join(" ")    
}    
    
fn main() {     
    println!("Hello, world!");    
    println!("{}", reverse_str(String::from("Hello, world!")));    
}