在 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 := char - 'a';

你可以"abxyz"转向

{0, 1, 23, 24, 25}.

如果你计算相邻字母之间的差异，你会得到

{-25, 1, 22, 1, 1}

（-25 是最后一个值和第一个值之间的差值。）有两个间隙：一个间隙是循环在 b 和 w 之间开始的间隙，另一个间隙是字母表换行的间隙。第二个间隙是差值为负的地方，总是在最后一项和第一项之间。您可以在差值上加上 26 来调整它，也可以使用模算术，其中使用余数%来计算环绕：

diff := ((p - q + 26) % 26;

如果第一个操作数为正，则强制%结果范围为 0 到 25。+ 26 强制其为正数。（下面的程序使用 25，因为您对分隔的定义不是位置的差异，而是两者之间的过滤器数量。）

现在你已经看到了差异

{1, 1, 22, 1, 1}

当最多只有两个不同的值并且其中一个最多出现一次时，就满足您的条件。（我发现这个条件测试起来非常复杂，见下文，但部分原因是 Go 的映射有点麻烦。）

无论如何，这是代码：

package main

import "fmt"

func list(str string) int {

    present := [26]bool{}

    pos := []int{}

    count := map[int]int{}

    // determine which letters exist

    for _, c := range str {

        if 'a' <= c && c <= 'z' {

            present[c-'a'] = true

        }

    }

    // concatenate all used letters (count sort, kinda)

    for i := 0; i < 26; i++ {

        if present[i] {

            pos = append(pos, i)

        }

    }

    // find differences

    q := pos[len(pos)-1]

    for _, p := range pos {

        diff := (p - q + 25) % 26

        count[diff]++

        q = p

    }

    // check whether input is a "rambai"

    if len(count) > 2 {

        return -1

    }

    which := []int{}

    occur := []int{}

    for k, v := range count {

        which = append(which, k)

        occur = append(occur, v)

    }

    if len(which) < 2 {

        return which[0]

    }

    if occur[0] != 1 && occur[1] != 1 {

        return -1

    }

    if occur[0] == 1 {

        return which[1]

    }

    return which[0]

}

func testme(str string) {

    fmt.Printf("\"%s\": %d\n", str, list(str))

}

func main() {

    testme("zzzzyyyybbbzzzaaaaaxxx")

    testme("yacegw")

    testme("keebeebheeh")

    testme("aco")

    testme("naan")

    testme("mississippi")

    testme("rosemary")

}

package main

import "fmt"

func list(str string) int {

    present := [26]bool{}

    pos := []int{}

    count := map[int]int{}

    // determine which letters exist

    for _, c := range str {

        if 'a' <= c && c <= 'z' {

            present[c-'a'] = true

        }

    }

    // concatenate all used letters (count sort, kinda)

    for i := 0; i < 26; i++ {

        if present[i] {

            pos = append(pos, i)

        }

    }

    // find differences

    q := pos[len(pos)-1]

    for _, p := range pos {

        diff := (p - q + 25) % 26

        count[diff]++

        q = p

    }

    // check whether input is a "rambai"

    if len(count) > 2 {

        return -1

    }

    which := []int{}

    occur := []int{}

    for k, v := range count {

        which = append(which, k)

        occur = append(occur, v)

    }

    if len(which) < 2 {

        return which[0]

    }

    if occur[0] != 1 && occur[1] != 1 {

        return -1

    }

    if occur[0] == 1 {

        return which[1]

    }

    return which[0]

}

func testme(str string) {

    fmt.Printf("\"%s\": %d\n", str, list(str))

}

func main() {

    testme("zzzzyyyybbbzzzaaaaaxxx")

    testme("yacegw")

    testme("keebeebheeh")

    testme("aco")

    testme("naan")

    testme("mississippi")

    testme("rosemary")

}

https://play.golang.org/p/ERhLxC_zfjl