在 Go 中按字母顺序查找相等分隔的字符串/单词

Question

我试图找到在字母表的圆形排列中等距分隔的单词/字符串。例如：

• “zzzzyyyybbbzzzaaaaaxxx”是由“xyzab”组成的列表，分隔符为 0 {xy, yz, za, ab}

• “aco” 是一个分隔符为 11 {co, oa} 的列表

因此，我想编写函数 IsSeparated(B) 并在 B 为“isSeparated”时返回 true

以下是我的代码/解决方案：

• 首先，我尝试删除字符串中的重复项，以便更容易计算间隔

• 其次，我按字母顺序对字符串进行排序

• 第三，排序后，我计算每个字母的间隔

• 在“isSeparated”方法中，我尝试通过使用使其以循环排列方式计数maxpair -1 == count，因为总会有 1 个字母没有配对，例如

• [{ab} {bx} {xy} {yz} {za}] - [{0} {21} {0} {0} {0}]]//there are 5 pairs = maxPair -1({-xy}

因此，由于它是圆形排列的，中间的总是奇数，即 21，与其余对的间隔不相等

这是变得棘手的部分，我似乎无法获得所需的输出。按字母顺序查找每个字母的长度/分隔并检查它们是否均匀分隔的正确方法可能是什么。

Answer 1

我不太明白你试图确定分离的部分。在 Go 中，就像在 C 中一样，您可以对字符进行算术运算。例如，您将获得每个小写字母的从 0 开始的索引：pos&nbsp;:=&nbsp;char&nbsp;-&nbsp;'a';你可以"abxyz"转向{0,&nbsp;1,&nbsp;23,&nbsp;24,&nbsp;25}.如果你计算相邻字母之间的差异，你会得到{-25,&nbsp;1,&nbsp;22,&nbsp;1,&nbsp;1}（-25 是最后一个值和第一个值之间的差值。）有两个间隙：一个间隙是循环在 b 和 w 之间开始的间隙，另一个间隙是字母表换行的间隙。第二个间隙是差值为负的地方，总是在最后一项和第一项之间。您可以在差值上加上 26 来调整它，也可以使用模算术，其中使用余数%来计算环绕：diff&nbsp;:=&nbsp;((p&nbsp;-&nbsp;q&nbsp;+&nbsp;26)&nbsp;%&nbsp;26;如果第一个操作数为正，则强制%结果范围为 0 到 25。+ 26 强制其为正数。（下面的程序使用 25，因为您对分隔的定义不是位置的差异，而是两者之间的过滤器数量。）现在你已经看到了差异{1,&nbsp;1,&nbsp;22,&nbsp;1,&nbsp;1}当最多只有两个不同的值并且其中一个最多出现一次时，就满足您的条件。（我发现这个条件测试起来非常复杂，见下文，但部分原因是 Go 的映射有点麻烦。）无论如何，这是代码：package mainimport "fmt"func list(str string) int {&nbsp; &nbsp; present := [26]bool{}&nbsp; &nbsp; pos := []int{}&nbsp; &nbsp; count := map[int]int{}&nbsp; &nbsp; // determine which letters exist&nbsp; &nbsp; for _, c := range str {&nbsp; &nbsp; &nbsp; &nbsp; if 'a' <= c && c <= 'z' {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; present[c-'a'] = true&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // concatenate all used letters (count sort, kinda)&nbsp; &nbsp; for i := 0; i < 26; i++ {&nbsp; &nbsp; &nbsp; &nbsp; if present[i] {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pos = append(pos, i)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // find differences&nbsp; &nbsp; q := pos[len(pos)-1]&nbsp; &nbsp; for _, p := range pos {&nbsp; &nbsp; &nbsp; &nbsp; diff := (p - q + 25) % 26&nbsp; &nbsp; &nbsp; &nbsp; count[diff]++&nbsp; &nbsp; &nbsp; &nbsp; q = p&nbsp; &nbsp; }&nbsp; &nbsp; // check whether input is a "rambai"&nbsp; &nbsp; if len(count) > 2 {&nbsp; &nbsp; &nbsp; &nbsp; return -1&nbsp; &nbsp; }&nbsp; &nbsp; which := []int{}&nbsp; &nbsp; occur := []int{}&nbsp; &nbsp; for k, v := range count {&nbsp; &nbsp; &nbsp; &nbsp; which = append(which, k)&nbsp; &nbsp; &nbsp; &nbsp; occur = append(occur, v)&nbsp; &nbsp; }&nbsp; &nbsp; if len(which) < 2 {&nbsp; &nbsp; &nbsp; &nbsp; return which[0]&nbsp; &nbsp; }&nbsp; &nbsp; if occur[0] != 1 && occur[1] != 1 {&nbsp; &nbsp; &nbsp; &nbsp; return -1&nbsp; &nbsp; }&nbsp; &nbsp; if occur[0] == 1 {&nbsp; &nbsp; &nbsp; &nbsp; return which[1]&nbsp; &nbsp; }&nbsp; &nbsp; return which[0]}func testme(str string) {&nbsp; &nbsp; fmt.Printf("\"%s\": %d\n", str, list(str))}func main() {&nbsp; &nbsp; testme("zzzzyyyybbbzzzaaaaaxxx")&nbsp; &nbsp; testme("yacegw")&nbsp; &nbsp; testme("keebeebheeh")&nbsp; &nbsp; testme("aco")&nbsp; &nbsp; testme("naan")&nbsp; &nbsp; testme("mississippi")&nbsp; &nbsp; testme("rosemary")}package mainimport "fmt"func list(str string) int {&nbsp; &nbsp; present := [26]bool{}&nbsp; &nbsp; pos := []int{}&nbsp; &nbsp; count := map[int]int{}&nbsp; &nbsp; // determine which letters exist&nbsp; &nbsp; for _, c := range str {&nbsp; &nbsp; &nbsp; &nbsp; if 'a' <= c && c <= 'z' {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; present[c-'a'] = true&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // concatenate all used letters (count sort, kinda)&nbsp; &nbsp; for i := 0; i < 26; i++ {&nbsp; &nbsp; &nbsp; &nbsp; if present[i] {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pos = append(pos, i)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; // find differences&nbsp; &nbsp; q := pos[len(pos)-1]&nbsp; &nbsp; for _, p := range pos {&nbsp; &nbsp; &nbsp; &nbsp; diff := (p - q + 25) % 26&nbsp; &nbsp; &nbsp; &nbsp; count[diff]++&nbsp; &nbsp; &nbsp; &nbsp; q = p&nbsp; &nbsp; }&nbsp; &nbsp; // check whether input is a "rambai"&nbsp; &nbsp; if len(count) > 2 {&nbsp; &nbsp; &nbsp; &nbsp; return -1&nbsp; &nbsp; }&nbsp; &nbsp; which := []int{}&nbsp; &nbsp; occur := []int{}&nbsp; &nbsp; for k, v := range count {&nbsp; &nbsp; &nbsp; &nbsp; which = append(which, k)&nbsp; &nbsp; &nbsp; &nbsp; occur = append(occur, v)&nbsp; &nbsp; }&nbsp; &nbsp; if len(which) < 2 {&nbsp; &nbsp; &nbsp; &nbsp; return which[0]&nbsp; &nbsp; }&nbsp; &nbsp; if occur[0] != 1 && occur[1] != 1 {&nbsp; &nbsp; &nbsp; &nbsp; return -1&nbsp; &nbsp; }&nbsp; &nbsp; if occur[0] == 1 {&nbsp; &nbsp; &nbsp; &nbsp; return which[1]&nbsp; &nbsp; }&nbsp; &nbsp; return which[0]}func testme(str string) {&nbsp; &nbsp; fmt.Printf("\"%s\": %d\n", str, list(str))}func main() {&nbsp; &nbsp; testme("zzzzyyyybbbzzzaaaaaxxx")&nbsp; &nbsp; testme("yacegw")&nbsp; &nbsp; testme("keebeebheeh")&nbsp; &nbsp; testme("aco")&nbsp; &nbsp; testme("naan")&nbsp; &nbsp; testme("mississippi")&nbsp; &nbsp; testme("rosemary")}https://play.golang.org/p/ERhLxC_zfjl