C++ 字符串的词法排名

2024 年 8 月 29 日 | 5 分钟阅读

在本文中，我们将讨论 C++ 中字符串的字典序排名。但在深入实现之前，我们必须了解什么是字典序。

字典序或字典顺序（通常称为字母或字典排列）是根据每个组成字母的字母顺序排列单词的方式。

问题陈述

查找字符串 str 在其所有修改（按字典序排序时）中的排名。

示例

Input: string = "cab"
Output: 5

解释：如果给定字符串的所有排列都按字典序组织，它们将看起来像 "abc", "acb", "bac", "bca", "cab" 和 "cba"。由此可见，字符串的排名是 5。

朴素的方法是按字典序生成所有排列，并保存当前字符串的排名。检查生成的排列是否与输入字符串匹配，并返回字符串的排名。

算法

Create a recursive function to calculate the factorial of a given number.
    fact(num):
        if num <= 1:
            return 1 return num * fact(num- 1)
    
Create a function that computes the rank of a string in lexicographic permutation order.
    find_Rank(st):
       Determine the length of the provided string.
        
 Set the rank to 1 at the start.
         Loop through the string's characters one by one.
         Create a variable to count the number of characters smaller than st[i].
         After st[i], loop over the characters.
         Update the rank based on the number of characters less than st[I].
Return the rank of the input string.

文件名：StringOrder.cpp

#include <bits/stdc++.h>
using namespace std;

// Create a recursive function to calculate the factorial for a given number.
int fact(int num) {
	//Initializing the base condition
	if(num <= 1) {
		return 1;
	}
	// Recursive case: return the number of times the factorial with a value of num-1.
	return num * fact(num - 1);
}

// Create a function that computes the rank of a string in lexicographic permutation order.
int findRanks(string str) {
	//Determine the length of the input string
	int num = str.length();
	// initialising the rank as 1
	int ranks = 1;
	// Every single character in the string is looped through.
	for(int i = 0; i < num; i++) {
		// Create a variable to count the number of characters smaller than str[i].
		int c = 0;

		// After str[I], loop over each character. 
		for(int j = i + 1; j < num; j++) {
			// If str[i] is higher than str[j], the count variable is increased.
			if(str[i] > str[j]) {
				c++;
			}
		}

		//The rank should be updated depending on the number of characters less than str[I] 
		// multiplied by the factorial corresponding to the number of available characters.
		ranks += c * fact(num - i - 1);
	}

	// The highest possible rank of the supplied string is returned.
	return ranks;
}
// Mail section
int main() {
	// defining the given input string
	string strs = "student";
	// Use the findRank function to find the position at the top of the test text and print the result.
	cout << findRanks(strs) << endl;
	//return 0 indicates that the program was completed.
	return 0;
}

输出

使用排列概念计算字符串的字典序排名

该问题可以使用排列概念解决，该概念基于以下思想：

确定当所有字符固定到该索引时，可以创建多少个字典序较小的字符串。它将返回比该字符串小的字符串，我们将能够确定排名。

要将此概念付诸实践，请执行以下操作：

从 i = 0 到字符串的长度遍历字符串
确定小于当前字符的字符数量。
计算字典序较小的字符串数量。
将该值添加到排名中。
最后，将排名乘以 1，并将结果作为所需答案返回。

文件名：StringOrder2.cpp

+=// C++ Program for finding the lexicographic order of the string
#include <bits/stdc++.h>
using namespace std;

//A utility function for calculating the factorial of the number
int facts(int num) { 
	return (num <= 1) ? 1 : num * facts(num - 1); 
}
// A utility function for counting the smaller characters to the right of the array[low].
int findtheSmallerInRight(string strs, int l, int h)
{
	int countRights = 0, i;

	for (i = l+ 1; i <= h; ++i)
		if (strs[i] < strs[l])
			++countRights;

	return countRights;
}

// A function for determining the rank of a string in all character combinations. 
int findtheRanks(string str)
{
	int length = str.size();
	int muls = facts(length);
	int ranks= 1;
	int countRights;

	int i;
	for (i = 0; i < length; ++i) {
		muls /= length - i;

		////Count the number of characters less than str[i] // from str[i+1] to str[length-1]
		countRights = findtheSmallerInRight(str, i, length - 1);

		ranks countRights * muls;
	}

	return ranks;
}

// Driver code
int main()
{
	string strs= "student";

	// Function calling
	cout << findtheRanks(strs);
	return 0;
}

输出

字符串的线性时间字典序排名

该解决方案的逻辑与上述技术相同。通过建立一个大小为 256 的辅助数组，可以减少时间复杂度。让我们创建一个数组，存储字符串中小于 第 i 个字符 的字符总数，并在字符串迭代期间，在给定字符串的每个索引之后更新它。

文件名：StringRank.cpp

//Program for finding the rank of a string using Linear Time complexity
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHAR 256

// a function for finding the factorial of a number
int fact(int num) { 
	return (num <= 1) ? 1 : num * fact(num- 1); 
}

// Create a count array with a value at each index.
// includes the number of smaller characters in the entire string
void populateAndIncreasingCount(int* c, string st)
{
	int i;

	for (i = 0; st[i]; ++i)
		++c[st[i]];

	for (i = 1; i < MAX_CHAR; ++i)
		c[i] += c[i - 1];
}

///Removes a character ch from the count[] array, which was created by populateAndIncreasingCount().
void updatecount(int* c, char ch)
{
	int i;
	for (i = ch; i < MAX_CHAR; ++i)
		--c[i];
}

 //A function for determining the rank of a string in all permutations of individual characters.
int findRanks(string st)
{
	int length = st.size();
	int muls = fact(length);
	int ranks = 1, i;

	//initialising with 0
	int c[MAX_CHAR] = { 0 };

	// Fill up the count array so that c[I] 
	// includes the count of characters in st 
	//that have a value less than i.
	populateAndIncreasingCount(c,st);

	for (i = 0; i < length; ++i) {
		muls /= length - i;

		
		ranks += c[st[i] - 1] * muls;

		//reducing the count
		updatecount(c, st[i]);
	}

	return ranks;
}

int main()
{
	string st = "student";

	// function calling
	cout << "The rank of the string is  "<<findRanks(st);
	return 0;
}

输出

The rank of the string is 2617

复杂度

时间复杂度：O(N)

空间复杂度：O(1)

下一主题C++ 中合并重叠区间

C++ 字符串的词法排名

问题陈述

使用排列概念计算字符串的字典序排名

字符串的线性时间字典序排名

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 字符串的词法排名

问题陈述

使用排列概念计算字符串的字典序排名

字符串的线性时间字典序排名

相关帖子

C++ 中使用线段树查找直方图中最大矩形面积

C++ STL 中 fill() 和 fill_n() 函数的区别

C++ 序列容器

C++ 匿名对象

C++ BFS 代码

C++ HASHSET

最佳 C++ 在线课程

C++ 值传递

C++ 复制省略

使用类将两个复数相加的 C++ 程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器