[Dart] 58. Length of Last Word

1. 문제

 

https://leetcode.com/problems/length-of-last-word/?envType=study-plan-v2&envId=top-interview-150

 

 

2. 요구사항

1) 단어와 공백으로 구성된 문자열 s가 주어진다.

2) 문자열 s의 마지막 단어의 길이를 반환한다.

3) 단, s는 영어 문자와 공백으로만 구성되며, 최소한 하나의 단어가 들어있다.

 

 

 

3. 핵심 아이디어

1) 문자열을 뒤에서부터 탐색

마지막 단어의 길이를 반환하는 것이기 때문에 문자열을 뒤에서부터 순회합니다.

 

res는 공백으로 분리된 단어를 저장하는 변수입니다.

 

문자열을 뒤에서부터 순회하며 마지막 단어의 길이를 찾습니다.

현재 문자가 공백이면 continue로 다음 문자로 넘어갑니다.

만약, 해당 문자가 공백이 아닐 경우, res에 문자를 추가합니다.

순회 후, 문자가 공백이고 res에 문자가 이미 추가되었다면 이 res의 길이를 반환합니다.

 

2) 코드

class Solution {
  int lengthOfLastWord(String s) {
    String res = "";

    for (var i = s.length-1; i >=0; i--) {
      if(s[i]== " " && res.isNotEmpty) return res.length; 
      if(s[i] == " ") {
        continue;
      }
      res+= s[i];
    }

    return res.length;
  }
}

 

시간 복잡도 : O(n)

- 문자열을 순회하기 때문

 

공간 복잡도 : O(n)

- res가 문자열을 저장하기 때문

 

만약, 'hello world '가 주어질 때,

가장 마지막 문자는 ' '공백입니다.

첫 번째 분기문에서 공백이지만 res가 비어있으므로 다음 분기문으로 넘어갑니다.

두 번째 분기문에서 공백이므로 다음 문자로 넘어갑니다.

 

다음 문자는 d입니다.

첫 번째 분기문에서 공백이 아니기 때문에 다음 분기문으로 넘어가고,

두 번째 분기문도 넘어갑니다.

그 후에야 res에 d를 저장합니다.

 

이렇게 가다 보면 res에는 dlrow가 저장됩니다.

결국, 마지막 단어의 길이만 필요하기에 문자의 순서는 상관없습니다.

 

 

3) trim과 split

trim()은 문자열의 앞 뒤에 있는 공백 제거(제거된 새 문자열 반환)하고,

split(String separator) 은 문자열에서 separator를 기준으로 분리합니다.

 

' fly me to the moon '이라는 문자열이 있다고 가정할 때, 이를 trim()으로 공백을 제거하면

'fly me to the moon'이 됩니다.

문자열의 앞 뒤만 공백을 제거하고, 가운데 있는 공백은 제거하지 못했습니다.

하지만 괜찮습니다. 우리는 마지막 단어의 길이가 필요하니까요.

 

그 후, 공백을 기준으로 문자열을 나누면

[fly, me, , , to, , , the, moon]이 됩니다.

우린 이 리스트의 마지막 요소의 길이를 반환하면 됩니다.

 

 

4) 코드

class Solution {
  int lengthOfLastWord(String s) {
    var splitString = s.trim().split(' ');

    return splitString.last.length;
  }
}

 

시간 복잡도 : O(n)

- split(' ') 연산을 통해 새로운 리스트를 생성하기 때문

 

공간 복잡도 : O(n)

- 문자열을 리스트로 변환하여 저장하기 때문