一、面试题 08.07. 无重复字符串的排列组合
中等
无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
示例1:
输入：S = “qwe”
输出：[“qwe”, “qew”, “wqe”, “weq”, “ewq”, “eqw”]
示例2:
输入：S = “ab”
输出：[“ab”, “ba”]
class S0807:
def func(self,nums):
result=[]
def dfs(path,used):
if len(nums)==len(path):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i]=True
path.append(nums[i])
dfs(path,used)
used[i]=False
path.pop()
dfs([],[False]*len(nums))
return [''.join(i) for i in result]
r=S0807()
nums="qqe"
print(r.func(nums))
二、面试题 10.02. 变位词组
中等
编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
注意：本题相对原题稍作修改
示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,“eat”,“tea”],
[“nat”,“tan”],
[“bat”]
]
class S1002:
def func(self, s):
dic = defaultdict(list)
for i in s:
key = ''.join(sorted(i))
dic[key].append(i)
return list(dic.values())
res = S1002()
s = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(res.func(s))
三、面试题 17.11. 单词距离
中等
有个内含单词的超大文本文件，给定任意两个不同的单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。
如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?
示例：
输入：words = [“I”,“am”,“a”,“student”,“from”,“a”,“university”,“in”,“a”,“city”],
word1 = “a”, word2 = “student”
输出：1
class S1711:
def func(self, words, word1, word2):
ans = inf
idx1 = inf # 正无穷
idx2 = -inf # 负无穷
for i, word in enumerate(words):
# print(i,word)
if word1 == word:
idx1 = i
elif word2 == word:
idx2 = i
ans = min(ans, abs(idx1 - idx2))
return ans
r = S1711()
words = ["I", "am", "a", "student", "from", "a", "university", "in", "a", "city"]
word1 = "a"
word2 = "student"
print(r.func(words, word1, word2))
四、LCR 014. 字符串的排列
中等
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
示例 1：
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
示例 2：
输入: s1= “ab” s2 = “eidboaoo”
输出: False
class S014:
def func(self, s1, s2):
s1_len = len(s1)
s2_len = len(s2)
for i in range(s2_len - s1_len + 1):
temp = s2[i:i + s1_len]
if temp == s1 or Counter(s1) == Counter(temp):
return True
return False
s = S014()
s1 = "ab"
s2 = "eidboaoo"
print(s.func(s1, s2))
五、LCR 020. 回文子串
中等
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
class S647:
def func(self,s):
dp=[[False]*len(s) for _ in range(len(s))]
result=0
# print(dp)
for i in range(len(s)-1,-1,-1):
for j in range(i,len(s)):
if s[i]==s[j]:
if j-i<=1:
result+=1
dp[i][j]=True
else:
if dp[i+1][j-1]==True:
result+=1
dp[i][j]=True
return result
r=S647()
s="aaa"
print(r.func(s))
六、1528. 重新排列字符串
简单
给你一个字符串 s 和一个 长度相同 的整数数组 indices 。
请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。
返回重新排列后的字符串。
示例 1：
输入：s = “codeleet”, indices = [4,5,6,7,0,2,1,3]
输出：“leetcode”
解释：如图所示，“codeleet” 重新排列后变为 “leetcode” 。
示例 2：
输入：s = “abc”, indices = [0,1,2]
输出：“abc”
解释：重新排列后，每个字符都还留在原来的位置上。
class S1528:
def func(self, s, indices):
res = list(zip(s, indices))
res1 = sorted(res, key=lambda x: x[
1]) # [('l', 0), ('e', 1), ('e', 2), ('t', 3), ('c', 4), ('o', 5), ('d', 6), ('e', 7)]
return ''.join([i[0] for i in res1])
r = S1528()
s = "abc"
indices = [0, 1, 2]
print(r.func(s, indices))
