数组中两个字符串的最小距离

数组中两个字符串的最小距离

字符串间最小距离

【题目】
给定一个字符串数组strs，再给定两个字符串str1和str2，返回在strs中str1与str2的最小距离，
如果str1或str2为null，或不在strs中，返回-1。

【举例】
strs=[“1”，“3”，“3”，“3”，“2”，“3”，“1”]，str1=“1”，str2=“2”，返回2。
strs=[“CD”]，str1=“CD”，str2=“AB”，返回-1。

【进阶题目】
如果查询发生的次数有很多，将每次查询的时间复杂度降为O（1）。

一次O(N)查询

遍历字符串数组strs，
last1记录最近str1位置，last2记录最近str2位置
若两者都存在，则与min_distance比较，存储较小值。
时间复杂度为$O(N)$O(N)。

相应代码

# O(N)查询strs中str1与str2的最小距离
def get_min_distance(strs, str1, str2):
    if str1 is None or str2 is None:
        return -1
    if str1 == str2:
        return 0
    last1 = -1  # 记录最近str1位置
    last2 = -1  # 记录最近str2位置
    min_distance = len(strs)  # 不可能的较大距离
    for i in range(len(strs)):
        if strs[i] == str1:
            last1 = i
            if last2 != -1:
                distance = last1 - last2
                if distance < min_distance:
                    min_distance = distance
        elif strs[i] == str2:
            last2 = i
            if last1 != -1:
                distance = last2 - last1
                if distance < min_distance:
                    min_distance = distance
    if min_distance == len(strs):
        return -1
    else:
        return min_distance
# 简单测试
if __name__ == '__main__':
    strs = ["1", "3", "3", "3", "2", "3", "1"]
    str1 = "1"
    str2 = "2"
    print(get_min_distance(strs, str1, str2))  # 2

    strs = ["CD"]
    str1 = "CD"
    str2 = "AB"
    print(get_min_distance(strs, str1, str2))  # -1

多次O(1)查询

若需进行多次查询，且要求常数时间查询，那么需要提前计算字符串数组strs中所有字符串之间的距离，并存储。
生成记录record{str1:{str2:min_distance}}，存储strs中str1与str2的最小距离，时间复杂度为$O(N^2)$O(N2)，空间复杂度为$O(N^2)$O(N2)
  遍历字符串数组strs，str_index存储strs中最新的字符串及其索引；
  计算str_index中字符串间的最小距离（计算遍历过的字符串间的最小距离）；
  str1: {str2: min_distance}与str2: {str1: min_distance}同步更新最小距离；
record[str1][str2]查询strs中str1与str2的最小距离，时间复杂度为$O(1)$O(1)。

相应代码

# O(1)查询strs中str1与str2的最小距离
# 生成记录{str1:{str2:min_distance}}，存储strs中str1与str2的最小距离，时间复杂度为O(N^2)，空间复杂度为O(N^2)
# record[str1][str2] 时间复杂度O(1)查询
class Record:
    def __init__(self, strs):
        self.record = {}  # {str1:{str2:min_distance}}
        str_index = {}  # {str:index}，strs中字符串及其索引
        for i in range(len(strs)):
            str1 = strs[i]
            str_index[str1] = i
            self.update(str_index, str1)  # 更新添加str1后的record

    def update(self, str_index, str1):
        str1_record = {}
        if str1 not in self.record:
            self.record[str1] = str1_record
        str1_record = self.record[str1]
        for str2, index2 in str_index.items():
            if str1 != str2:
                index1 = str_index[str1]
                distance = index1 - index2
                str2_record = self.record[str2]
                if str2 in str1_record:
                    if distance < str1_record[str2]:
                        str1_record[str2] = distance
                        str2_record[str1] = distance
                else:
                    str1_record[str2] = distance
                    str2_record[str1] = distance

    def get_min_distance(self, str1, str2):
        if str1 is None or str2 is None:
            return -1
        elif str1 == str2:
            return 0
        else:
            if str1 in self.record and str2 in self.record[str1]:
                return self.record[str1][str2]
            else:
                return -1
# 简单测试
if __name__ == '__main__':
    strs = ["1", "3", "3", "3", "2", "3", "1"]
    str1 = "1"
    str2 = "2"
    record = Record(strs)
    print(record.get_min_distance(str1, str2))  # 2

    strs = ["CD"]
    str1 = "CD"
    str2 = "AB"
    record = Record(strs)
    print(record.get_min_distance(str1, str2))  # -1

有任何疑问和建议，欢迎在评论区留言和指正！

感谢您所花费的时间与精力！