在 Go 中按字母顺序查找等分 string/words

Question

我试图找到 words/strings 在字母表的圆形排列中等距分布的。例如：

“zzzzyyyybbbzzzaaaaaxxx”是一个由“xyzab”组成的列表，间隔为 0 {xy, yz, za, ab}
“aco”是一个分隔为 11 {co, oa}的列表

因此，我想编写函数 IsSeparated(B) 并在 B 为 "isSeparated"

时返回 true

下面是我的 codes/solution:

首先，我尝试删除字符串中的重复项，以便更容易计算间隔
其次，我按字母顺序对字符串进行排序
第三，排序后，我计算每个字母的间隔
在 "isSeparated" 方法中，我试图通过使用 maxpair -1 == count 使其在循环排列中计数，因为总会有 1 个字母没有配对，例如
[{ab} {bx} {xy} {yz} {za}] - [{0} {21} {0} {0} {0}]]//there are 5 pairs = maxPair -1({-xy}

因此，由于是循环排列，所以中间的那对永远是奇数，也就是21，与其余的对不等分

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


package main

import (
    "fmt"
    "strings"
)

//Q3
func separationCount(x, y string) int {
    alphabets := [26]string{"a","b","c","d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u","v", "w", "x", "y", "z"}
    separation := 0

    for i:=0; i < len(alphabets); i++{
        if x == alphabets[i]{

            for j:= i+1; j <len(alphabets); j++{
            if y == alphabets[i+1]{
            fmt.Println(separation)
            return separation
            }else{
                i++
                separation++
            } 
            }
                }else{
            //do nothing
        }
    }
    //fmt.Println(separation)
    return 0
}

func isSeparated(B [] string) bool {
    var N int = len(B) - 1
    var maxPair int
    var item1 string
    var item2 string
    var separation int = 0 
    count := 0
    var intialSeparation int

    //calling the methods
    fmt.Println("Original array:",B)
    B = removeDuplicates(B)
    B = sortedList(B)

    item1 = B[0]
    item2 = B[1]
    intialSeparation = separationCount(item1,item2)

    for i := 0; i< N; i++{
        item1 = B[i]
        item2 = B[i + 1]

        separation = separationCount(item1,item2)
        maxPair++
        if intialSeparation == separation{
            count++
        }

        if maxPair == count{
            return true
        }else{
            return false
        }

    }
    return false
}

//to sort the alphabets 
func sortedList(B []string) [] string {
    N  := len(B)
    //max := 0
    element1 := 0 
    element2 := 1

    for element2 < N {
        var item1 string = B[element1]
        var item2 string = B[element2]

        //using function call
        if greater(item1, item2){
            B[element1] = item2
            B[element2] = item1
        }
        element1++
        element2++
    } 
    fmt.Println("Alphabetically sorted:", B )
    return B
}

//for sorting
func greater(a, b string) bool {
    if strings.ToLower(a) > strings.ToLower(b) {
      return true
    } else {
      return false
    }
  }

  //removing duplicates
func removeDuplicates(B []string) []string {
    encountered := map[string]bool{}

    // Create a map of all unique elements.
    for v:= range B {
        encountered[B[v]] = true
    }

    // Place all keys from the map into a slice.
    result := []string{}
    for key, _ := range encountered {
        result = append(result, key)
    }
    fmt.Println("Duplicates removed:", result )
    return result
}

func main(){
    //q3
    B := []string{"y", "a", "a", "a", "c", "e", "g", "w", "w", "w"}
    fmt.Println(isSeparated(B))
}

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，因为你定义的separation不是位置的不同，而是中间间隔的个数。）

现在你有了不同之处

{1, 1, 22, 1, 1}

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

无论如何，这是代码：

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

在 Go 中按字母顺序查找等分 string/words

Finding equally separated string/words in alphabetical order in Go

algorithm

go

alphabetical