前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2021-08-14:给定两个字符串S和T,返回S的所有子序列中有多少个子序列的字面值等于T。

2021-08-14:给定两个字符串S和T,返回S的所有子序列中有多少个子序列的字面值等于T。

作者头像
福大大架构师每日一题
发布2021-09-03 15:23:06
5180
发布2021-09-03 15:23:06
举报

2021-08-14:给定两个字符串S和T,返回S的所有子序列中有多少个子序列的字面值等于T。

福大大 答案2021-08-14:

样本对应模型。

时间复杂度:O(N^2)。

空间复杂度:O(N^2)。

代码用golang编写。代码如下:

代码语言:javascript
复制
package main

import "fmt"

func main() {
    s := "1122"
    t := "12"
    ret := numDistinct1(s, t)
    fmt.Println(ret)
}

func numDistinct1(S string, T string) int {
    return process(S, T, len(S), len(T))
}

func process(s string, t string, i int, j int) int {
    if j == 0 {
        return 1
    }
    if i == 0 {
        return 0
    }
    res := process(s, t, i-1, j)
    if s[i-1] == t[j-1] {
        res += process(s, t, i-1, j-1)
    }
    return res
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class17/Code04_DistinctSubseq.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-14,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档