2024-09-07：用go语言，给定一个包含 n 个非空字符串的数组 arr，你的任务是找出一个长度为 n 的字符串数组 answer。

满足以下条件：

对于每个索引 i，answer[i] 是 arr[i] 的最短子字符串，并且这个子字符串不是 arr 中其他字符串的子字符串。

如果有多个这样的子字符串，则选择字典序最小的一个。

如果不存在这样的子字符串，则对应位置的 answer[i] 应为一个空字符串。

你需要编写一个算法来实现以上要求，并返回生成的字符串数组 answer。

输入：arr = [“cab”,“ad”,“bad”,“c”]。

输出：[“ab”,"",“ba”,""]。

解释：求解过程如下：

对于字符串 “cab” ，最短没有在其他字符串中出现过的子字符串是 “ca” 或者 “ab” ，我们选择字典序更小的子字符串，也就是 “ab” 。

对于字符串 “ad” ，不存在没有在其他字符串中出现过的子字符串。

对于字符串 “bad” ，最短没有在其他字符串中出现过的子字符串是 “ba” 。

对于字符串 “c” ，不存在没有在其他字符串中出现过的子字符串。

答案2024-09-07：

chatgpt

题目来自leetcode3076。

大体步骤如下：

Go完整代码如下：

package main

import (
	"fmt"
	"strings"
)

func shortestSubstrings(arr []string) []string {
	ans := make([]string, len(arr))
	for i, s := range arr {
		m := len(s)
		res := ""
		for size := 1; size <= m && res == ""; size++ {
		next:
			for k := size; k <= m; k++ {
				sub := s[k-size : k]
				if res != "" && sub >= res {
					continue
				}
				for j, t := range arr {
					if j != i && strings.Contains(t, sub) {
						continue next
					}
				}
				res = sub
			}
		}
		ans[i] = res
	}
	return ans
}

func main() {
	arr := []string{"cab", "ad", "bad", "c"}
	fmt.Println(shortestSubstrings(arr))
}

Rust完整代码如下：

use std::collections::HashSet;

fn shortest_substrings(arr: Vec<&str>) -> Vec<String> {
    let mut ans = vec![String::new(); arr.len()];

    for (i, s) in arr.iter().enumerate() {
        let m = s.len();
        let mut res = String::new();

        for size in 1..=m {
            if !res.is_empty() {
                break;
            }
            for k in size..=m {
                let sub = &s[k - size..k];
                if !res.is_empty() && sub >= res.as_str() {
                    continue;
                }
                let mut found = false;

                for (j, t) in arr.iter().enumerate() {
                    if j != i && t.contains(sub) {
                        found = true;
                        break;
                    }
                }

                if !found {
                    res = sub.to_string();
                }
            }
        }
        ans[i] = res;
    }

    ans
}

fn main() {
    let arr = vec!["cab", "ad", "bad", "c"];
    println!("{:?}", shortest_substrings(arr));
}