首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

2024-08-03:用go语言,给定一个从 0 开始的字符串数组 `words`, 我们定义一个名为 `isPrefixAndSuffix` 的布尔函数,该函数接受两个字符串参数 `str1` 和

编程知识
2024年08月03日 17:04

2024-08-03:用go语言,给定一个从 0 开始的字符串数组 words

我们定义一个名为 isPrefixAndSuffix 的布尔函数,该函数接受两个字符串参数 str1str2

str1 同时是 str2 的前缀和后缀时,函数返回 true;否则返回 false

例如,isPrefixAndSuffix("aba", "ababa") 返回 true

因为 "aba" 既是 "ababa" 的前缀也是后缀,而 isPrefixAndSuffix("abc", "abcd") 返回 false

我们的目标是以整数形式返回符合条件的下标对 (i, j) 的数量,

其中满足 i < jisPrefixAndSuffix(words[i], words[j])true

输入:words = ["a","aba","ababa","aa"]。

输出:4。

解释:在本示例中,计数的下标对包括:

i = 0 且 j = 1 ,因为 isPrefixAndSuffix("a", "aba") 为 true 。

i = 0 且 j = 2 ,因为 isPrefixAndSuffix("a", "ababa") 为 true 。

i = 0 且 j = 3 ,因为 isPrefixAndSuffix("a", "aa") 为 true 。

i = 1 且 j = 2 ,因为 isPrefixAndSuffix("aba", "ababa") 为 true 。

因此,答案是 4 。

答案2024-08-03:

chatgpt

题目来自leetcode3045。

大体步骤如下:

1 定义函数 isPrefixAndSuffix(str1, str2):实现一个函数,判断 str1 是否是 str2 的前缀和后缀。

  • 检查 str1 的长度是否大于 str2 的长度。如果是,直接返回 false

  • 确定 str2 的前缀是否与 str1 相同。

  • 确定 str2 的后缀是否与 str1 相同。

  • 如果上述两个条件都满足,返回 true;否则返回 false

2.遍历字符串数组 words

  • 使用两个嵌套循环,外层循环设定为 i,从 0 遍历到 len(words)-1,内层循环设定为 j,从 i+1 遍历到 len(words)-1。这样可以确保 i < j

3.调用 isPrefixAndSuffix 函数:在每对 (i, j) 中,调用 isPrefixAndSuffix(words[i], words[j])

  • 如果函数返回 true,则计数器增加 1。

4.返回计数器的值:最终,返回计数器的值,即为符合条件的下标对数量。

总时间复杂度

  • 外层循环走 n 次,内层循环从 i+1n,最坏情况下为 O(n)

  • 对于每一对 (i, j),调用 isPrefixAndSuffix 需要在 O(m) 时间内进行字符串的比较,其中 m 是前缀或后缀的长度。

  • 因此,总的时间复杂度为 O(n^2 * m),其中 m 是字符串的最长长度。

总额外空间复杂度

  • 本算法使用少量的额外空间来存储计数器和函数的一些局部变量,因此额外空间复杂度为 O(1)
  • 函数内部的字符串比较不需要额外的存储,仅使用常量空间来存储临时变量,主存储体在输入 words 中。

综上所述,时间复杂度为 O(n^2 * m),额外空间复杂度为 O(1)

Go完整代码如下:

在package main

import (
	"fmt"
)

func countPrefixSuffixPairs(words []string) (ans int64) {
	type pair struct{ x, y byte }
	type node struct {
		son map[pair]*node
		cnt int
	}
	root := &node{son: map[pair]*node{}}
	for _, s := range words {
		cur := root
		for i := range s {
			p := pair{s[i], s[len(s)-1-i]}
			if cur.son[p] == nil {
				cur.son[p] = &node{son: map[pair]*node{}}
			}
			cur = cur.son[p]
			ans += int64(cur.cnt)
		}
		cur.cnt++
	}
	return
}


func main() {
	words:=[]string{"a","aba","ababa","aa"}
	fmt.Println(countPrefixSuffixPairs(words))
}

在这里插入图片描述

Python完整代码如下:

# -*-coding:utf-8-*-

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0

def count_prefix_suffix_pairs(words):
    root = TrieNode()
    ans = 0

    for s in words:
        current = root
        length = len(s)
        
        for i in range(length):
            p = (s[i], s[length - 1 - i])  # 使用元组表示前缀和后缀字符对
            if p not in current.children:
                current.children[p] = TrieNode()
            current = current.children[p]
            ans += current.count  # 统计满足条件的对数
        current.count += 1  # 更新当前节点的计数

    return ans

if __name__ == "__main__":
    words = ["a", "aba", "ababa", "aa"]
    print(count_prefix_suffix_pairs(words))

在这里插入图片描述

From:https://www.cnblogs.com/moonfdd/p/18340866
本文地址: http://www.shuzixingkong.net/article/753
0评论
提交 加载更多评论
其他文章 OpenCV计算机视觉学习(16)——仿射变换学习笔记
如果需要其他图像处理的文章及代码,请移步小编的GitHub地址 传送门:请点击我 如果点击有误:https://github.com/LeBron-Jian/ComputerVisionPractice 在计算机视觉和图像处理中,仿射变换是一种重要的几何变换方法。它可以通过线性变换和平移来改变图像的
OpenCV计算机视觉学习(16)——仿射变换学习笔记 OpenCV计算机视觉学习(16)——仿射变换学习笔记 OpenCV计算机视觉学习(16)——仿射变换学习笔记
Blazor Web 应用如何实现Auto模式
本文介绍Blazor Web应用Auto交互呈现模式的实现方案,如下示例是基于 Known 框架来实现的,该解决方案共有3个项目,具体实现步骤如下: 1. 前后端共用项目 创建前后端共用类库项目Sample,定义系统的实体类、数据模型、服务接口、常量、枚举等,项目工程文件内容如下: &lt;Proj
实现一个终端文本编辑器来学习golang语言:序言
欢迎!这个系列的博文会带你使用golang语言来编写一个你自己的文本编辑器。 首先想说说写这个系列文章的动机。 其实作为校招生加入某头部互联网大厂一转眼已经快4年了。可以说该大厂算是比较早的用golang语言作为主要后端开发技术栈的公司了,绝大部分后端项目的语言选型都是golang。最近一年会发现许
实现一个终端文本编辑器来学习golang语言:序言
小狐狸Chatgpt付费创作系统>=2.8.0 0day任意文件上传漏洞
小狐狸Chatgpt付费创作系统>=2.8.0 0day任意文件上传漏洞 小狐狸Chatgpt付费创作系统>=2.8.0 0day任意文件上传漏洞 小狐狸Chatgpt付费创作系统>=2.8.0 0day任意文件上传漏洞
iOS开发基础146-深入解析WKWebView
WKWebView是苹果在iOS 8中引入的重要组件,它替代了UIWebView,为开发者提供了高性能、高稳定性的网页显示和交互能力。在本文中,我们将深入探讨WKWebView的底层架构、关键特性、使用方法和高级功能。 一、WKWebView的底层架构 WKWebView基于WebKit框架,采用多
FFmpeg在游戏视频录制中的应用:画质与文件大小的综合比较
我们游戏内的视频录制目前只支持avi固定码率,在玩家见面会上有玩家反馈希望改善录制画质,我最近在研究了有关视频画质的一些内容并做了一些统计。 录制视频大小对比 首先在游戏引擎中增加了对录制mp4格式的支持,并且使用h246编码可以直接在网页上播放无法再做转码 测试场景:视频尺寸固定大小为: 1904
实现一个终端文本编辑器来学习golang语言:第二章Raw模式下的输入输出
从第二章开始,在每个小节的最后都会有一些代码实操作业,你可以选择自己完成(比较推荐),再对照我的实现方式,当然也可以直接看我的代码实现。不过,之后的各个功能实现,我都会基于我先前的代码实现版本,在它的基础上进行扩展。 首先,我们先来解决第一章遗留的第一个问题:输入数据会被stdin缓存,直到遇到换行
实现一个终端文本编辑器来学习golang语言:第二章Raw模式下的输入输出
[rCore学习笔记 021]多道程序与分时任务
写在前面 本随笔是非常菜的菜鸡写的。如有问题请及时提出。 可以联系:1160712160@qq.com GitHhub:https://github.com/WindDevil (目前啥也没有 导读 这里就是第三章的开头了,由于我的巨菜,导致天天半天理解不了关键点所在,唉,实在是太折磨人. 遵照上一
[rCore学习笔记 021]多道程序与分时任务 [rCore学习笔记 021]多道程序与分时任务 [rCore学习笔记 021]多道程序与分时任务