---

一、面试题 08.07. 无重复字符串的排列组合

中等
无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

示例1:
输入：S = “qwe”
输出：[“qwe”, “qew”, “wqe”, “weq”, “ewq”, “eqw”]

示例2:
输入：S = “ab”
输出：[“ab”, “ba”]

class S0807:
    def func(self, s):
        perm = set(permutations(s))
        return [''.join(p) for p in perm]


r = S0807()
s = "qwe"
print(r.func(s))

itertools.permutation()：它指的是可以对集合或字符串进行排序或排列的所有可能的组合
用法:
permutations(iterator, r)

from itertools import  permutations
a = 'abc'   #对字符串进行permutations排列组合
for i in permutations(a,3):
    x = ''.join(i)
    print (x,end=' ')
print ('\n------------------------------------')

二、面试题 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 Solution:
    def countSubstrings(self, s: str) -> int:
        def check_chr(s, left, right, con):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
                con += 1
            return con

        res = 0
        for i in range(len(s)):
            con1 = check_chr(s, i, i, 0)  # 以当前索引位置为中心，获取存在的所有回文数
            con2 = check_chr(s, i, i + 1, 0)  # 以当前索引位置和当前索引位置的下一位置为中心，获取存在的所有回文数
            res += con1 + con2

        return res

六、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))

---