当前位置: 首页 > 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 …...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...