LeetCode //C - 1071. Greatest Common Divisor of Strings
1071. Greatest Common Divisor of Strings
For two strings s and t, we say “t divides s” if and only if s = t + … + t (i.e., t is concatenated with itself one or more times).
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
Example 1:
Input: str1 = “ABCABC”, str2 = “ABC”
Output: “ABC”
Example 2:
Input: str1 = “ABABAB”, str2 = “ABAB”
Output: “AB”
Example 3:
Input: str1 = “LEET”, str2 = “CODE”
Output: “”
Constraints:
- 1 <= str1.length, str2.length <= 1000
- str1 and str2 consist of English uppercase letters.
From: LeetCode
Link: 1071. Greatest Common Divisor of Strings
Solution:
Ideas:
-
Check Concatenation Equality: Concatenate str1 with str2 and str2 with str1. If these concatenated strings are not equal, there is no common divisor string and we should return an empty string.
-
Find the GCD of the Lengths: If the strings pass the first check, find the GCD of the lengths of the two strings.
-
Create and Return the GCD String: The GCD string is a substring of either string with length equal to the GCD of the lengths of the two strings.
Code:
// Function to find the greatest common divisor of two integers
int gcd(int a, int b) {while (b != 0) {int t = b;b = a % b;a = t;}return a;
}// Function to find the greatest common divisor of two strings
char* gcdOfStrings(char* str1, char* str2) {int len1 = strlen(str1), len2 = strlen(str2);// Allocate memory for concatenated stringschar *concat1 = (char *)malloc(sizeof(char) * (len1 + len2 + 1));char *concat2 = (char *)malloc(sizeof(char) * (len1 + len2 + 1));// Concatenate str1 and str2strcpy(concat1, str1);strcat(concat1, str2);// Concatenate str2 and str1strcpy(concat2, str2);strcat(concat2, str1);// Check if concatenated strings are equalif (strcmp(concat1, concat2) != 0) {free(concat1);free(concat2);return "";}free(concat1);free(concat2);int gcdLength = gcd(len1, len2);char *result = (char *)malloc(sizeof(char) * (gcdLength + 1));strncpy(result, str1, gcdLength);result[gcdLength] = '\0';return result;
}
相关文章:
LeetCode //C - 1071. Greatest Common Divisor of Strings
1071. Greatest Common Divisor of Strings For two strings s and t, we say “t divides s” if and only if s t … t (i.e., t is concatenated with itself one or more times). Given two strings str1 and str2, return the largest string x such that x divides …...
智能优化算法应用:基于群居蜘蛛算法3D无线传感器网络(WSN)覆盖优化 - 附代码
智能优化算法应用:基于群居蜘蛛算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用:基于群居蜘蛛算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.群居蜘蛛算法4.实验参数设定5.算法结果6.…...
AtCoder Beginner Contest 332
E - Lucky bag(简单状态压缩dp) 题目链接 题意:给你n个物品,m个福袋,让你将这n个物品用m个福袋打包(福袋可以为空),让分完之后的总方差最小,输出最小方差。 思路:其实由题目的数据…...
华为OD试题二(文件目录大小、相对开音节、找最小数)
1. 文件目录大小 题目描述: 一个文件目录的数据格式为:目录id,本目录中文件大小,(子目录id 列表)。其中目录id全局唯一,取值范围[1,200],本目录中文件大小范 围[1,1000],子目录id列表个数[0,10…...
【Spark精讲】Spark作业执行原理
基本流程 用户编写的Spark应用程序最开始都要初始化SparkContext。 用户编写的应用程序中,每执行一个action操作,就会触发一个job的执行,一个应用程序中可能会生成多个job执行。一个job如果存在宽依赖,会将shuffle前后划分成两个…...
Docker容器:Centos7搭建Docker镜像私服harbor
目录 1、安装docker 1.1、前置条件 1.2、查看当前操作系统的内核版本 1.3、卸载旧版本(可选) 1.4、安装需要的软件包 1.5、设置yum安装源 1.6、查看docker可用版本 1.7、安装docker 1.8、开启docker服务 1.9、安装阿里云镜像加速器 1.10、设置docker开机自启 2、安…...
ClickHouse安装和部署
ClickHouse安装过程: ClickHouse支持运行在主流64位CPU架构(X86、AArch和PowerPC)的Linux操作 系统之上,可以通过源码编译、预编译压缩包、Docker镜像和RPM等多种方法进行安装。由于篇幅有限,本节着重讲解离线RPM的安…...
Spring Cloud Gateway中对admin端点进行认证
前言 我们被扫了一个漏洞,SpringBoot Actuator 未授权访问,漏洞描述是这样的: Actuator 是 springboot 提供的用来对应用系统进行自省和监控的功能模块,借助于 Actuator 开发者可以很方便地对应用系统某些监控指标进行查看、统计…...
2. 如何通过公网IP端口映射访问到设备的vmware虚拟机的ubuntu服务器
文章目录 1. 主机设备是Windows 11系统2. 安装vmware虚拟机3. 创建ubuntu虚拟机(据说CentOS 7 明年就不维护了,就不用这个版本的linux了)4. 安装nginx服务:默认端口805. 安装ssh服务:默认端口226. 设置主机 -> ubuntu的端口映射7. 设置路由…...
配置android sudio出现的错误
导入demo工程,配置过程参考: AndroidStudio导入项目的正确方式,修改gradle配置 错误:Namespace not specified. Specify a namespace in the module’s build file. 并定位在下图位置: 原因:Android 大括号…...
【初阶C++】前言
C前言 1. 什么是C2. C发展史3. C的重要性4. 如何学习C 1. 什么是C C语言是结构化和模块化的语言,适合处理较小规模的程序。对于复杂的问题,规模较大的程序,需要高度的抽象和建模时,C语言则不合适。为了解决软件危机, …...
MAC IDEA Maven Springboot
在mac中,使用idea进行maven项目构建 环境配置如何运行maven项目1.直接在IDEA中运行2.使用jar打包后执行 如何搭建spring boot1.添加依赖2.创建入口类3.创建控制器4. 运行5.其他 环境配置 官网安装IDEA使用IDEA的创建新项目选择创建MAEVEN项目测试IDEA的MAVEN路径是…...
Angular13无法在浏览器debug
前言 本文将介绍如何解决在Angular 13中无法在浏览器中进行调试的问题,并提供了一种解决方法。 发生场景 根据项目需求,升级至Angular 13后,发现无法在浏览器中进行调试。 问题原因 无法进行调试的原因是,当使用Angular 13的…...
H.264与H.265(HEVC):视频编码的演进
目录 H.264的发展历程 1. 标准发布 2. 广泛应用 3. 专业化应用 H.265的出现...
Python从入门到精通九:Python异常、模块与包
了解异常 什么是异常 当检测到一个错误时,Python解释器就无法继续执行了,反而出现了一些错误的提示,这就是所谓的“异常”, 也就是我们常说的BUG bug单词的诞生 早期计算机采用大量继电器工作,马克二型计算机就是这样的。 19…...
无需公网IP联机Minecraft,我的世界服务器本地搭建教程
目录 前言 1.Mcsmanager安装 2.创建Minecraft服务器 3.本地测试联机 4. 内网穿透 4.1 安装cpolar内网穿透 4.2 创建隧道映射内网端口 5.远程联机测试 6. 配置固定远程联机端口地址 6.1 保留一个固定TCP地址 6.2 配置固定TCP地址 7. 使用固定公网地址远程联机 8.总…...
机器学习-SVM(支持向量机)
推荐课程:【机器学习实战】第5期 支持向量机 |数据分析|机器学习|算法|菊安酱_哔哩哔哩_bilibili 赞美菊神ヾ ( ゜ⅴ゜)ノ 一、什么是支持向量机? 支持向量机(Support Vector Machine, SVM)是一类按监督学习࿰…...
保姆级:Windows Server 2012上安装.NET Framework 3.5
📚📚 🏅我是默,一个在CSDN分享笔记的博主。📚📚 🌟在这里,我要推荐给大家我的专栏《Windows》。🎯🎯 🚀无论你是编程小白,还是有…...
昇腾910安装驱动出错,降低Centos7.6的内核版本
零、问题描述: 在安装Atlas800-9000服务器的驱动的时候,可能会出现错误:Dkms install failed, details in : /var/log/ascend_seclog/ascend_install.log 如下所示: [rootlocalhost ~]# ./Ascend-hdk-910-npu-driver_23.0.rc3_l…...
LeetCode刷题日志-73矩阵置零
思路一: 用一个同样大小的矩阵记录0的位置,然后遍历矩阵置0, 空间复杂度为O(mn) class Solution {public void setZeroes(int[][] matrix) {int [][] matrix_new new int[matrix.length][matrix[0].length];for(int …...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
