[python 刷题] 271 Encode and Decode Strings

[python 刷题] 271 Encode and Decode Strings

题目：

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

string encode(vector<string> strs) {// ... your codereturn encoded_string;
}

Machine 2 (receiver) has the function:

vector<string> decode(string s) {
//... your code
return strs;
}

So Machine 1 does:

string encoded_string = encode(strs);

and Machine 2 does:

vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

You are not allowed to solve the problem using any serialize methods (such as eval).

简单的说，就是讲一个数组转化成字符串，再将字符串转换成数组，并且保证输入输出是一样的问题。

题目中有提到，strs[i] contains any possible characters out of 256 valid ASCII characters，所以最暴利的解法就是使用非 ASCII 字符去做分隔符，比如说中文：

class Codec:def encode(self, strs: List[str]) -> str:"""Encodes a list of strings to a single string."""return '中'.join(strs)def decode(self, s: str) -> List[str]:"""Decodes a single string to a list of strings."""return s.split('中')# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(strs))

不过题目也有一个 follow up：

Follow up: Could you write a generalized algorithm to work on any possible set of characters?

这道题在求一个 generic 的解法，其中一个解决思路是使用当前字符串的长度加上一个特殊符号作为分隔符，并将其加到字符串前/后就可以解决这个问题。

诚然求一个 generic 的情况，可能说会有同样的符号出现在字符串中，不过只要找第一个合法的分隔符即可，如这里使用 数字+ # 的组合去做分隔符，就算字符串包含 数字+ # 的组合，如：[63#, 2#]，在计算的时候依旧可以通过获取字符串的长度，将其拼接成：3#63#2#2#。在解码时，首先读取第一个 数字+ # 的组合，得到 3#，并就此确认第一个字符串的长度为 3，进而还原 63#，以此类推。

这题的解法也是找的，我自己写不出这么漂亮的 python 代码：

class Codec:def encode(self, strs):return ''.join(map(lambda s: f"{len(s)}#{s}", strs))def decode(self, s):res = []i = 0while i < len(s):j = iwhile s[j] != '#':j += 1length = int(s[i:j])i = j + 1j = i + lengthres.append(s[i:j])i = jreturn res

这里有几个知识点：

1. map()

   map() 是一个 python 内置的函数，可以返回一个 iterable，其语法为 map(function, iterable, ...)，其中 function 会执行 iterable 中的每一个值

   如需要将一个数组转换成数组的平方，即 [1,2,3,4,5] 转换为 [1x1, 2x2, 3x3, 4x4, 5x5]，就可以用 map() 去实现：

    def square(num):return num * numl = [1, 2, 3, 4, 5]res = map(square, l)print(res)for num in res:print(num)
   

   结果为：

   <map object at 0x1009273d0>
   1
   4
   9
   16
   25
   

2. lambda

   lambda 是一个 python 中创建匿名方式的方法，就是快，如上面的 def square(num) 用 lambda 重写为：

   lambda x: x*xres = map(lambda x: x*x, l)
   

   其结果是一样的

3. f-string

   f-string 是 python3.6 介绍的新特性，简单的说就是用来 format 字符串，其语法就是用 f"" 指代这是一个 f-string，花括号中则是可以添加变量

   所以这里的 f"{len(s)}#{s}" 代表着拼接：字符串的长度，#，和当前字符串

4. s[i:j]

   这个则是一个 string 的 slice 方法，这里会将字符串的数字 slice 下来，并且使用 int() 转换成数字，这样就能获取当前字符串的长度了

   整体流程就是，从左到右读取第一个数字（当前字符串的长度），一直到 #，获取当前字符串的长度，截取字符串，并且将其推到 list 中，重复操作