Add all possible solutions into an array and find the one with minimum difference.

- standard situation: [:mid] + [mid] + reversed([:mid])
- some times: [:mid] + [mid digit value +1] + reversed([:mid])
- some times: [:mid] + [mid digit value -1] + reversed([:mid])
- when the string is not palindrome: [:mid] + [mid] + reversed([:mid])
- some times: result is 1 digit shorter than original string. In that case the solution have be something like 9...9, for example 11 -> 9, 100->99 etc.

```
class Solution(object):
def nearestPalindromic(self, n):
"""
:type n: str
:rtype: str
"""
if n <= '10':
return str(int(n)-1)
inputs = [str(10**(len(n)-1)-1), str(int(n) - 10**(len(n)/2)), str(int(n) + 10**(len(n)/2))] + ([n] if n != n[::-1] else [])
return min([i[:len(i)-len(i)/2] + i[:len(i)/2][::-1] for i in inputs], key = lambda a: (abs(int(a) - int(n)), int(a)))
```