当前位置: 首页 > news >正文

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:
  1. 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.

  2. Find the GCD of the Lengths: If the strings pass the first check, find the GCD of the lengths of the two strings.

  3. 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)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于群居蜘蛛算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于群居蜘蛛算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.群居蜘蛛算法4.实验参数设定5.算法结果6.…...

AtCoder Beginner Contest 332

E - Lucky bag(简单状态压缩dp&#xff09; 题目链接 题意&#xff1a;给你n个物品&#xff0c;m个福袋&#xff0c;让你将这n个物品用m个福袋打包(福袋可以为空&#xff09;&#xff0c;让分完之后的总方差最小&#xff0c;输出最小方差。 思路&#xff1a;其实由题目的数据…...

华为OD试题二(文件目录大小、相对开音节、找最小数)

1. 文件目录大小 题目描述&#xff1a; 一个文件目录的数据格式为&#xff1a;目录id&#xff0c;本目录中文件大小&#xff0c;(子目录id 列表)。其中目录id全局唯一&#xff0c;取值范围[1,200]&#xff0c;本目录中文件大小范 围[1,1000]&#xff0c;子目录id列表个数[0,10…...

【Spark精讲】Spark作业执行原理

基本流程 用户编写的Spark应用程序最开始都要初始化SparkContext。 用户编写的应用程序中&#xff0c;每执行一个action操作&#xff0c;就会触发一个job的执行&#xff0c;一个应用程序中可能会生成多个job执行。一个job如果存在宽依赖&#xff0c;会将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安装过程&#xff1a; ClickHouse支持运行在主流64位CPU架构&#xff08;X86、AArch和PowerPC&#xff09;的Linux操作 系统之上&#xff0c;可以通过源码编译、预编译压缩包、Docker镜像和RPM等多种方法进行安装。由于篇幅有限&#xff0c;本节着重讲解离线RPM的安…...

Spring Cloud Gateway中对admin端点进行认证

前言 我们被扫了一个漏洞&#xff0c;SpringBoot Actuator 未授权访问&#xff0c;漏洞描述是这样的&#xff1a; Actuator 是 springboot 提供的用来对应用系统进行自省和监控的功能模块&#xff0c;借助于 Actuator 开发者可以很方便地对应用系统某些监控指标进行查看、统计…...

2. 如何通过公网IP端口映射访问到设备的vmware虚拟机的ubuntu服务器

文章目录 1. 主机设备是Windows 11系统2. 安装vmware虚拟机3. 创建ubuntu虚拟机&#xff08;据说CentOS 7 明年就不维护了&#xff0c;就不用这个版本的linux了&#xff09;4. 安装nginx服务:默认端口805. 安装ssh服务:默认端口226. 设置主机 -> ubuntu的端口映射7. 设置路由…...

配置android sudio出现的错误

导入demo工程&#xff0c;配置过程参考&#xff1a; AndroidStudio导入项目的正确方式&#xff0c;修改gradle配置 错误&#xff1a;Namespace not specified. Specify a namespace in the module’s build file. 并定位在下图位置&#xff1a; 原因&#xff1a;Android 大括号…...

【初阶C++】前言

C前言 1. 什么是C2. C发展史3. C的重要性4. 如何学习C 1. 什么是C C语言是结构化和模块化的语言&#xff0c;适合处理较小规模的程序。对于复杂的问题&#xff0c;规模较大的程序&#xff0c;需要高度的抽象和建模时&#xff0c;C语言则不合适。为了解决软件危机&#xff0c; …...

MAC IDEA Maven Springboot

在mac中&#xff0c;使用idea进行maven项目构建 环境配置如何运行maven项目1.直接在IDEA中运行2.使用jar打包后执行 如何搭建spring boot1.添加依赖2.创建入口类3.创建控制器4. 运行5.其他 环境配置 官网安装IDEA使用IDEA的创建新项目选择创建MAEVEN项目测试IDEA的MAVEN路径是…...

Angular13无法在浏览器debug

前言 本文将介绍如何解决在Angular 13中无法在浏览器中进行调试的问题&#xff0c;并提供了一种解决方法。 发生场景 根据项目需求&#xff0c;升级至Angular 13后&#xff0c;发现无法在浏览器中进行调试。 问题原因 无法进行调试的原因是&#xff0c;当使用Angular 13的…...

H.264与H.265(HEVC):视频编码的演进

目录 H.264的发展历程 1. 标准发布 2. 广泛应用 3. 专业化应用 H.265的出现...

Python从入门到精通九:Python异常、模块与包

了解异常 什么是异常 当检测到一个错误时&#xff0c;Python解释器就无法继续执行了&#xff0c;反而出现了一些错误的提示&#xff0c;这就是所谓的“异常”, 也就是我们常说的BUG bug单词的诞生 早期计算机采用大量继电器工作&#xff0c;马克二型计算机就是这样的。 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(支持向量机)

推荐课程&#xff1a;【机器学习实战】第5期 支持向量机 |数据分析|机器学习|算法|菊安酱_哔哩哔哩_bilibili 赞美菊神ヾ ( ゜ⅴ゜)&#xff89; 一、什么是支持向量机&#xff1f; 支持向量机&#xff08;Support Vector Machine, SVM&#xff09;是一类按监督学习&#xff0…...

保姆级:Windows Server 2012上安装.NET Framework 3.5

&#x1f4da;&#x1f4da; &#x1f3c5;我是默&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; ​​ &#x1f31f;在这里&#xff0c;我要推荐给大家我的专栏《Windows》。&#x1f3af;&#x1f3af; &#x1f680;无论你是编程小白&#xff0c;还是有…...

昇腾910安装驱动出错,降低Centos7.6的内核版本

零、问题描述&#xff1a; 在安装Atlas800-9000服务器的驱动的时候&#xff0c;可能会出现错误&#xff1a;Dkms install failed, details in : /var/log/ascend_seclog/ascend_install.log 如下所示&#xff1a; [rootlocalhost ~]# ./Ascend-hdk-910-npu-driver_23.0.rc3_l…...

LeetCode刷题日志-73矩阵置零

思路一&#xff1a; 用一个同样大小的矩阵记录0的位置&#xff0c;然后遍历矩阵置0&#xff0c; 空间复杂度为O&#xff08;mn&#xff09; class Solution {public void setZeroes(int[][] matrix) {int [][] matrix_new new int[matrix.length][matrix[0].length];for(int …...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...

渗透实战PortSwigger Labs指南:自定义标签XSS和SVG XSS利用

阻止除自定义标签之外的所有标签 先输入一些标签测试&#xff0c;说是全部标签都被禁了 除了自定义的 自定义<my-tag onmouseoveralert(xss)> <my-tag idx onfocusalert(document.cookie) tabindex1> onfocus 当元素获得焦点时&#xff08;如通过点击或键盘导航&…...

运动控制--BLDC电机

一、电机的分类 按照供电电源 1.直流电机 1.1 有刷直流电机(BDC) 通过电刷与换向器实现电流方向切换&#xff0c;典型应用于电动工具、玩具等 1.2 无刷直流电机&#xff08;BLDC&#xff09; 电子换向替代机械电刷&#xff0c;具有高可靠性&#xff0c;常用于无人机、高端家电…...

迁移科技3D视觉系统:重塑纸箱拆垛场景的智能革命

一、传统拆垛场景的困局与破局之道 在汽车零部件仓库中&#xff0c;每天有超过2万只异形纸箱需要拆垛分拣。传统人工拆垛面临三大挑战&#xff1a; 效率瓶颈&#xff1a;工人每小时仅能处理200-300件&#xff0c;且存在间歇性疲劳安全隐患&#xff1a;20kg以上重箱搬运导致年…...