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

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

时间:2024-08-03 18:05:58浏览次数:17  
标签:03 函数 str1 words 字符串 true isPrefixAndSuffix

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))

在这里插入图片描述

标签:03,函数,str1,words,字符串,true,isPrefixAndSuffix
From: https://www.cnblogs.com/moonfdd/p/18340866

相关文章

  • 可验证随机函数 vrf 概述
    一、什么是VRF背景:在传统的区块链中,常用的随机算法是基于伪随机数生成器(PseudorandomNumberGenerator,PRNG)的。PRNG是一种确定性算法,它根据一个初始种子生成一个看似随机的序列。在区块链中,通常使用的是伪随机数序列来选择区块的创建者、确定验证节点的轮换顺序等。然而......
  • 20240803题解
    话说T3都把式子推出来了结果忘记差分约束怎么写了。光线(light)题面:有\(n\)个玻璃板,第\(i\)个玻璃板的透光率为\(a_i\%\),反射率为\(b_i\%\),有大小为\(1\)个单位的一束光从第\(1\)个玻璃板开始,有多少光能穿透\(n\)层玻璃板。题解:考虑\(n=2\)时,可以简单算出两个玻璃板组合后的反......
  • Python中定义(创建)、调用函数及返回值
    1.定义(创建)函数要调用一个函数,首先要定义它。在Python中使用关键字def来定义一个函数。函数通常由函数名、参数列表以及一系列语句组成的函数体构成的。函数定义的一般格式如下:def函数名(参数列表):函数体例如:defsayhello(): print('hello')最简单的函数:defm......
  • python用List的内建函数list.sort进行排序
    对List进行排序,Python提供了两个方法方法1用List的内建函数listsort进行排序listsort(func=None,key=None,reverse=False)Python实对List进行排序,Python提供了两个方法方法1.用List的内建函数list.sort进行排序list.sort(func=None,key=None,reverse=False)>>>list=......
  • C++ 面向对象基础-构造函数
    目录1.构造函数1.1基本使用1.2函数参数默认值1.3构造初始化列表 1.4隐式调用构造函数2.拷贝构造函数2.1概念2.2浅拷贝2.3深拷贝3.析构函数1.构造函数1.1基本使用构造函数是一种特殊的成员函数,用于创建对象时初始化,写法上有以下要求:●函数名称必......
  • 【JS】自调用函数怎么用?
    自调用函数定义自调用函数,也称为立即执行函数表达式(IIFE),是一种在定义后立即执行的函数(也就是说不用另外调用执行了)。它的主要目的是创建一个新的作用域,避免全局变量的污染。优势可以立即执行,不需要等待其他代码的执行。创建了新的作用域,可以保护内部的变量和函数不被外部......
  • 函数名冲突导致的C语言“conflicting types”编译错误
    快速解答:啊,看来你也遇到了“conflictingtypes”——类型冲突编译错误。如果你不是遇到:循环引用而没有用宏定义来解决。声明或定义在调用后面。声明和定义冲突。.h.gch未更新。那么我想告诉你,你可跟我一样忘了C语言不支持“函数重载”,即你的函数名不能重复。所......
  • Python中15个递归函数经典案例解析
    1.阶乘计算阶乘是一个常见的递归应用,定义为n!=n*(n-1)*…*1。deffactorial(n):ifn==0:return1else:returnn*factorial(n-1)print(factorial(5))#输出:1202.斐波那契数列斐波那契数列的每一项都......
  • 如何将 f 字符串转换为 .format()?
    我有这个函数,它使用f字符串来打印许多变量:defmyfunc(*args,**kwargs):if'fruit'and'juice'inkwargs:print(f"Ilike{'and'.join(args)}andmyfavoritefruitis{kwargs['fruit']}")print(f"M......
  • Shell编程——函数 和 输入/输出重定向
    文章目录Shell函数Shell输入/输出重定向输出重定向输入重定向重定向深入讲解/dev/null文件Shell函数shell中函数的定义格式如下:[function]funname[()]{ action: [returnint;]}参数说明:1、可以带functionfun()定义,也可以直接fun()定义,不带任何......