2023-05-23:如果交换字符串 X 中的两个不同位置的字母,使得它和字符串 Y 相等, 那么称 X 和 Y 两个字符串相似

举报
福大大架构师每日一题 发表于 2023/05/23 21:27:25 2023/05/23
【摘要】 2023-05-23:如果交换字符串 X 中的两个不同位置的字母,使得它和字符串 Y 相等,那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的,那它们也是相似的。例如,“tars” 和 “rats” 是相似的 (交换 0 与 2 的位置);“rats” 和 “arts” 也是相似的,但是 “star” 不与 “tars”,“rats”,或 “arts” 相似。总之,它们通过相似...

2023-05-23:如果交换字符串 X 中的两个不同位置的字母,使得它和字符串 Y 相等,

那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的,那它们也是相似的。

例如,“tars” 和 “rats” 是相似的 (交换 0 与 2 的位置);

“rats” 和 “arts” 也是相似的,但是 “star” 不与 “tars”,“rats”,或 “arts” 相似。

总之,它们通过相似性形成了两个关联组:{“tars”, “rats”, “arts”} 和 {“star”}。

注意,“tars” 和 “arts” 是在同一组中,即使它们并不相似。

形式上,对每个组而言,要确定一个单词在组中,只需要这个词和该组中至少一个单词相似。

给你一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个字母异位词。

请问 strs 中有多少个相似字符串组?

输入:strs = [“tars”,“rats”,“arts”,“star”]。

输出:2。

答案2023-05-23:

具体过程如下:

1.定义一个结构体 UnionFind,包含以下字段:

  • Father []int:每个元素的父节点;

  • Size []int:每个子集的大小;

  • Help []int:帮助数组;

  • Sets int:集合数量。

2.编写函数 NewUnionFind(n int) *UnionFind,创建一个新的并查集,需传入元素数量 n,实现如下:

  • 创建一个 UnionFind 结构体 uf,分别用 make 函数初始化父节点数组、子集大小数组和帮助数组,将集合数量 Sets 初始化为元素数量 n

  • 遍历每个元素,将其父节点初始化为自身,子集大小初始化为1。

  • 返回 uf

3.编写函数 Find(i int) int 实现路径压缩的查找操作,返回元素 i 所在集合的根节点,具体步骤如下:

  • 定义辅助变量 hi 为0;

  • 如果元素 i 的父节点不是它本身,将 i 加入帮助数组,将 i 更新为其父节点;

  • i 的父节点等于它本身时,表明已经到达集合的根节点,遍历帮助数组,依次将这些元素的父节点更新为根节点;

  • 返回根节点。

4.编写函数 Union(i, j int) 实现按秩合并的操作,将元素 i 所在集合和元素 j 所在集合合并成一个集合,具体步骤如下:

  • 分别查找元素 i 和元素 j 所在集合的根节点,如果它们所在的集合已经相同,则不需要合并;

  • 否则,比较两个集合的大小,将小的集合合并到大的集合中,并更新父节点和子集大小,同时将集合数量减1。

5.编写函数 Sets0() int 返回当前并查集中集合的数量,直接返回结构体字段 Sets 的值即可。

6.编写函数 numSimilarGroups(strs []string) int,遍历每对字符串,如果它们属于不同的集合,判断它们是否相似,如果是相似的则将它们合并到同一个集合中,最终返回并查集中剩余的集合数量,具体步骤如下:

  • 创建一个新的并查集 uf,元素数量为输入字符串列表 strs 的长度;

  • 遍历输入字符串列表 strs,对于每一对字符串 s1s2,判断它们是否属于同一个集合,如果不是,则比较它们是否相似,如果是相似的,则将它们所在集合合并;

  • 返回并查集中集合的数量。

7.在 main 函数中,给定输入字符串列表 strs,调用 numSimilarGroups 函数计算相似字符串组的数量,并输出结果。

时间复杂度:在最坏情况下,需要枚举任意两个字符串进行比较,因此需要 O ( n 2 m ) O(n^2m) 的时间复杂度,其中 n n 是字符串数组 strs 中字符串的数量, m m 是字符串的长度。并查集合并操作的时间复杂度为 α ( n ) \alpha(n) ,其中 α ( n ) \alpha(n) 是反阿克曼函数的某个很小的值,可以看作是常数级别的时间复杂度,因此对总时间复杂度的贡献可以忽略不计。因此,最终的时间复杂度为 O ( n 2 m ) O(n^2m)

空间复杂度:主要由并查集所用的空间和额外的辅助变量所占用的空间构成。其中,并查集需要的空间是 O ( n ) O(n) ,辅助变量 Help 需要的空间也是 O ( n ) O(n) ,因此总的空间复杂度为 O ( n ) O(n)

go语言完整代码如下:

package main

import "fmt"

func numSimilarGroups(strs []string) int {
	n, m := len(strs), len(strs[0])
	uf := NewUnionFind(n)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if uf.Find(i) != uf.Find(j) {
				diff := 0
				for k := 0; k < m && diff < 3; k++ {
					if strs[i][k] != strs[j][k] {
						diff++
					}
				}
				if diff == 0 || diff == 2 {
					uf.Union(i, j)
				}
			}
		}
	}
	return uf.Sets0()
}

type UnionFind struct {
	Father []int
	Size   []int
	Sets   int
	Help   []int
}

func NewUnionFind(n int) *UnionFind {
	uf := &UnionFind{
		Father: make([]int, n),
		Size:   make([]int, n),
		Help:   make([]int, n),
		Sets:   n,
	}
	for i := 0; i < n; i++ {
		uf.Father[i] = i
		uf.Size[i] = 1
	}
	return uf
}

func (uf *UnionFind) Find(i int) int {
	hi := 0
	for i != uf.Father[i] {
		uf.Help[hi] = i
		hi++
		i = uf.Father[i]
	}
	for hi > 0 {
		hi--
		uf.Father[uf.Help[hi]] = i
	}
	return i
}

func (uf *UnionFind) Union(i, j int) {
	fi, fj := uf.Find(i), uf.Find(j)
	if fi != fj {
		if uf.Size[fi] >= uf.Size[fj] {
			uf.Father[fj] = fi
			uf.Size[fi] += uf.Size[fj]
		} else {
			uf.Father[fi] = fj
			uf.Size[fj] += uf.Size[fi]
		}
		uf.Sets--
	}
}

func (uf *UnionFind) Sets0() int {
	return uf.Sets
}

func main() {
	strs := []string{"tars", "rats", "arts", "star"}
	res := numSimilarGroups(strs)
	fmt.Println(res)
}

在这里插入图片描述

rust完整代码如下:

fn main() {
    let strs = vec![
        "tars".to_string(),
        "rats".to_string(),
        "arts".to_string(),
        "star".to_string(),
    ];
    let res = num_similar_groups(strs);
    println!("{}", res);
}

fn num_similar_groups(strs: Vec<String>) -> i32 {
    let n = strs.len();
    let m = strs[0].len();
    let mut uf = UnionFind::new(n);
    for i in 0..n {
        for j in i + 1..n {
            // [i] [j]
            if uf.find(i) != uf.find(j) {
                let mut diff = 0;
                for k in 0..m {
                    if strs[i].as_bytes()[k] != strs[j].as_bytes()[k] {
                        diff += 1;
                    }
                    if diff >= 3 {
                        break;
                    }
                }
                if diff == 0 || diff == 2 {
                    uf.union(i, j);
                }
            }
        }
    }
    uf.sets() as i32
}

struct UnionFind {
    father: Vec<usize>,
    size: Vec<i32>,
    help: Vec<usize>, // 添加help字段
    sets: usize,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        let mut father = vec![0; n];
        let size = vec![1; n];
        for i in 0..n {
            father[i] = i;
        }
        Self {
            father,
            size,
            help: vec![0; n], // 初始化help
            sets: n,
        }
    }

    fn find(&mut self, i: usize) -> usize {
        let mut hi = 0;
        let mut j = i;
        while j != self.father[j] {
            self.help[hi] = j;
            hi += 1;
            j = self.father[j];
        }
        while hi > 0 {
            hi -= 1;
            self.father[self.help[hi]] = j;
        }
        j
    }

    fn union(&mut self, i: usize, j: usize) {
        let fi = self.find(i);
        let fj = self.find(j);
        if fi != fj {
            if self.size[fi] >= self.size[fj] {
                self.father[fj] = fi;
                self.size[fi] += self.size[fj];
            } else {
                self.father[fi] = fj;
                self.size[fj] += self.size[fi];
            }
            self.sets -= 1;
        }
    }

    fn sets(&self) -> usize {
        self.sets
    }
}

在这里插入图片描述

c语言完整代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* father;
    int* size;
    int* help;
    int sets;
} UnionFind;

UnionFind* newUnionFind(int n) {
    UnionFind* uf = (UnionFind*)malloc(sizeof(UnionFind));
    uf->father = (int*)malloc(sizeof(int) * n);
    uf->size = (int*)malloc(sizeof(int) * n);
    uf->help = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        uf->father[i] = i;
        uf->size[i] = 1;
    }
    uf->sets = n;
    return uf;
}

int find(UnionFind* uf, int i) {
    int hi = 0;
    while (i != uf->father[i]) {
        uf->help[hi++] = i;
        i = uf->father[i];
    }
    while (hi != 0) {
        hi--;
        uf->father[uf->help[hi]] = i;
    }
    return i;
}

void unionSet(UnionFind* uf, int i, int j) {
    int fi = find(uf, i);
    int fj = find(uf, j);
    if (fi != fj) {
        if (uf->size[fi] >= uf->size[fj]) {
            uf->father[fj] = fi;
            uf->size[fi] += uf->size[fj];
        }
        else {
            uf->father[fi] = fj;
            uf->size[fj] += uf->size[fi];
        }
        uf->sets--;
    }
}

int getSets(UnionFind* uf) {
    return uf->sets;
}

int numSimilarGroups(char** strs, int strsSize) {
    int n = strsSize, m = strlen(strs[0]);
    UnionFind* uf = newUnionFind(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (find(uf, i) != find(uf, j)) {
                int diff = 0;
                for (int k = 0; k < m && diff < 3; k++) {
                    if (strs[i][k] != strs[j][k]) {
                        diff++;
                    }
                }
                if (diff == 0 || diff == 2) {
                    unionSet(uf, i, j);
                }
            }
        }
    }
    return getSets(uf);
}

int main() {
    char* strs[] = { "tars", "rats", "arts", "star" };
    int strsSize = sizeof(strs) / sizeof(strs[0]);
    int res = numSimilarGroups(strs, strsSize);
    printf("%d\n", res); // 输出 2
    return 0;
}

在这里插入图片描述

c++完整代码如下:

#include <iostream>
#include <vector>
using namespace std;

class UnionFind {
public:
    vector<int> father;
    vector<int> size;
    vector<int> help;
    int sets;

    UnionFind(int n) : father(n), size(n, 1), help(n), sets(n) {
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }

    int find(int i) {
        int hi = 0;
        while (i != father[i]) {
            help[hi++] = i;
            i = father[i];
        }
        while (hi != 0) {
            father[help[--hi]] = i;
        }
        return i;
    }

    void unionSet(int i, int j) {
        int fi = find(i);
        int fj = find(j);
        if (fi != fj) {
            if (size[fi] >= size[fj]) {
                father[fj] = fi;
                size[fi] += size[fj];
            }
            else {
                father[fi] = fj;
                size[fj] += size[fi];
            }
            sets--;
        }
    }

    int getSets() {
        return sets;
    }
};

int numSimilarGroups(vector<string>& strs) {
    int n = strs.size(), m = strs[0].size();
    UnionFind uf(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (uf.find(i) != uf.find(j)) {
                int diff = 0;
                for (int k = 0; k < m && diff < 3; k++) {
                    if (strs[i][k] != strs[j][k]) {
                        diff++;
                    }
                }
                if (diff == 0 || diff == 2) {
                    uf.unionSet(i, j);
                }
            }
        }
    }
    return uf.getSets();
}

int main() {
    vector<string> strs = { "tars", "rats", "arts", "star" };
    int res = numSimilarGroups(strs);
    cout << res << endl;
    return 0;
}

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。