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

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

Qwen系列之Qwen3解读:最强开源模型的细节拆解

文章目录 1.1分钟快览2.模型架构2.1.Dense模型2.2.MoE模型 3.预训练阶段3.1.数据3.2.训练3.3.评估 4.后训练阶段S1: 长链思维冷启动S2: 推理强化学习S3: 思考模式融合S4: 通用强化学习 5.全家桶中的小模型训练评估评估数据集评估细节评估效果弱智评估和民间Arena 分析展望 如果…...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...