(Leetcode) 271 - String Encode and Decode
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
- 문제
문자열 배열을 하나의 문자열로 합치고, 다시 문자열 배열로 되돌리면 되는 문제이다.
내가 작성한 풀이
url encoding 방식을 활용하였다.
java에서는 기본적으로 URLEncoder, URLDecoder 클래스를 제공해주지만, 문제 내에서 사용하지 못하였기에 최소한으로 구현하여 대체하였다.
먼저 ‘,’ 에 대한 처리가 중요한데 ‘,’ 의 경우 url encode 를 하면 ‘%2C’ 로 변경된다. 해당 부분을 replace 처리해주도록 하였다. 이때 기존에 ‘%’ 라는 문자가 있는 케이스가 있을 것 같아서 ‘%’ 를 ‘%25’로 변경해주었다.
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(str.replace("%", "%25").replace(",", "%2C")).append(",");
}
return sb.length() > 0 ? sb.toString() : "";
}
public List<String> decode(String str) {
List<String> decodedList = new ArrayList<>();
if (str.length() > 0) {
int commaIndex = str.indexOf(",");
while (commaIndex > -1) {
decodedList.add(str.substring(0, commaIndex).replace("%2C", ",").replace("%25", "%"));
str = str.substring(commaIndex + 1);
commaIndex = str.indexOf(",");
}
}
return decodedList;
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(n * m)이다. (m은 각 문자열 길이의 평균)
비슷한 방식
json stringify 를 이용해도 될 것 이다.