# 最短回文串
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1:
输入:s = "aacecaaa"
输出:"aaacecaaa"
示例 2:
输入:s = "abcd"
输出:"dcbabcd"
提示:
0 <= s.length <= 5 * 104
s
仅由小写英文字母组成
## template
```python
class Solution:
def shortestPalindrome(self, s: str) -> str:
N = len(s)
idx1 = 0
for idx2 in range(N - 1, -1, -1):
if s[idx1] == s[idx2]:
idx1 += 1
if idx1 == N:
return s
return s[idx1:][::-1] + self.shortestPalindrome(s[:idx1]) + s[idx1:]
```
## 答案
```python
```
## 选项
### A
```python
```
### B
```python
```
### C
```python
```