Go-最长子序列&最长可能子序列

• 最长子序列（string为例）

package main

import "fmt"

func main() {
    // 实现：最长子序列
    str := "casso"
    strList := []string{
        "ca",
        "hha",
        "cass",
        "cassos",
    }
    fmt.Println(long(str, strList)) // cass
}

func long(s string, list []string) (max string) {
    for _, v := range list {
        if compare(s, v) {
            max = v
        }
    }
    return max
}

func compare(s, target string) bool {
    if s == "" || target == "" {
        return false
    }
    for i := 0; i < len(s) && i < len(target); i++ {
        if s[i] != target[i] {
            return false
        }
    }
    return len(s) > len(target) // 存在target长度超过s的可能（cassos）,但是cassos并不属于s的子集
}

• 最长可能子序列

package main

import (
    "fmt"
)

func main() {
    // 实现：可能子序列（删除str中一些字符后是否能与strList元素形成子序列关系）
    str := "cawqtweswesos"
    strList := []string{
        "ca",
        "hha",
        "casso",
        "cassos",
    }
    fmt.Println(long(str, strList)) // [ca casso cassos]
}

func long(s string, list []string) (res []string) {
    for _, v := range list {
        if compare(s, v) {
            res = append(res, v)
        }
    }
    return
}

func compare(s, target string) bool {
    if s == "" || target == "" {
        return false
    }
    i, j := 0, 0
    for i < len(s) && j < len(target) {
        if s[i] == target[j] { //相等则指针往右移动
            j++
        }
        i++
    }
    return j == len(target) // 指针移动步数跟目标字符串相同，说明存在子集可能
}