資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究移除最小長度子串以使給定字串成為迴文
迴文是指正讀和反讀都一樣的字元序列。在計算機科學和程式設計中，迴文是字串操作問題的常見主題。在本文中，我們將探討查詢必須從給定字串中移除的最小長度子串以使其成為迴文的問題。我們將包含一個示例來說明測試用例。
問題陳述
給定一個長度為'n'的字串's'，我們需要找到應移除的子串的最小長度，以使剩餘的字串成為迴文。
演算法
建立一個名為isPalindrome的函式，該函式接受字串's'作為引數，如果它是迴文則返回true，否則返回false。
建立一個名為minSizeSubstringToRemove的函式，該函式接受字串's'作為引數。
將變數'minSize'初始化為字串的長度。
使用迴圈遍歷字串，將索引'i'從0遞增到'n'。
在每次迭代中，執行以下步驟：
建立兩個子串：一個是從字串的開頭到索引'i'，另一個是從索引'i'到字串的結尾。
檢查任一子串是否為迴文。
如果任一子串是迴文，則將'minSize'更新為'minSize'和非迴文子串長度之間的最小值。
返回'minSize'作為結果。
示例
以下是此演算法在各種程式語言中的實現：
#include <stdio.h>
#include <string.h>
// Function to check if a string is a palindrome
int isPalindrome(const char *s, int left, int right) {
while (left < right) {
if (s[left] != s[right]) {
return 0;
}
++left;
--right;
}
return 1;
}
// Function to find the minimum size substring to be removed
int minSizeSubstringToRemove(const char *s) {
int n = strlen(s);
int minSize = n;
for (int i = 0; i <= n; ++i) {
// Splitting the string into left and right substrings
char leftSubstring[100];
strncpy(leftSubstring, s, i);
leftSubstring[i] = '\0';
char rightSubstring[100];
strncpy(rightSubstring, s + i, n - i);
rightSubstring[n - i] = '\0';
if (isPalindrome(leftSubstring, 0, i - 1)) {
minSize = (n - i) < minSize ? (n - i) : minSize;
}
if (isPalindrome(rightSubstring, 0, n - i - 1)) {
minSize = i < minSize ? i : minSize;
}
}
return minSize;
}
int main() {
char s[] = "abccbaab";
int result = minSizeSubstringToRemove(s);
printf("Minimum size substring to be removed: %d\n", result);
return 0;
}
輸出
Minimum size substring to be removed: 2
#include <iostream>
#include <string>
#include <algorithm>
// Function to check if a string is a palindrome
bool isPalindrome(const std::string &s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s[left] != s[right]) {
return false;
}
++left;
--right;
}
return true;
}
// Function to find the minimum size substring to be removed
int minSizeSubstringToRemove(std::string s) {
int n = s.length();
int minSize = n;
for (int i = 0; i <= n; ++i) {
std::string leftSubstring = s.substr(0, i);
std::string rightSubstring = s.substr(i, n - i);
if (isPalindrome(leftSubstring)) {
minSize = std::min(minSize, static_cast<int>(rightSubstring.length()));
}
if (isPalindrome(rightSubstring)) {
minSize = std::min(minSize, static_cast<int>(leftSubstring.length()));
}
}
return minSize;
}
int main() {
std::string s = "abccbaab";
int result = minSizeSubstringToRemove(s);
std::cout << "Minimum size substring to be removed: " << result << std::endl;
return 0;
}
輸出
Minimum size substring to be removed: 2
public class Main {
// Function to check if a string is a palindrome
private static boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// Function to find the minimum size substring to be removed
private static int minSizeSubstringToRemove(String s) {
int n = s.length();
int minSize = n;
for (int i = 0; i <= n; i++) {
String leftSubstring = s.substring(0, i);
String rightSubstring = s.substring(i, n);
if (isPalindrome(leftSubstring, 0, i - 1)) {
minSize = Math.min(minSize, n - i);
}
if (isPalindrome(rightSubstring, 0, n - i - 1)) {
minSize = Math.min(minSize, i);
}
}
return minSize;
}
public static void main(String[] args) {
String s = "abccbaab";
int result = minSizeSubstringToRemove(s);
System.out.println("Minimum size substring to be removed: " + result);
}
}
輸出
Minimum size substring to be removed: 2
# Function to check if a string is a palindrome
def is_palindrome(s, left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
# Function to find the minimum size substring to be removed
def min_size_substring_to_remove(s):
n = len(s)
min_size = n
for i in range(n + 1):
left_substring = s[:i]
right_substring = s[i:]
if is_palindrome(left_substring, 0, i - 1):
min_size = min(min_size, n - i)
if is_palindrome(right_substring, 0, n - i - 1):
min_size = min(min_size, i)
return min_size
s = "abccbaab"
result = min_size_substring_to_remove(s)
print("Minimum size substring to be removed:", result)
輸出
Minimum size substring to be removed: 2
測試用例示例
考慮以下字串：“abccbaab”。可能的子串及其各自的迴文狀態如下：
左子串 = ""，右子串 = "abccbaab"，迴文 = false
左子串 = "a"，右子串 = "bccbaab"，迴文 = false
左子串 = "ab"，右子串 = "ccbaab"，迴文 = false
左子串 = "abc"，右子串 = "cbaab"，迴文 = false
左子串 = "abcc"，右子串 = "baab"，迴文 = false
左子串 = "abccb"，右子串 = "aab"，迴文 = true (左子串)
左子串 = "abccba"，右子串 = "ab"，迴文 = true (左子串)
左子串 = "abccbaa"，右子串 = "b"，迴文 = false
左子串 = "abccbaab"，右子串 = ""，迴文 = false
從上面的迭代中，我們可以看出，要移除的最小長度子串是2，當左子串是“abccba”而右子串是“ab”時發生這種情況。在這種情況下，移除右子串“ab”將使剩餘的字串“abccba”成為迴文。
結論
在本文中，我們探討了查詢必須從給定字串中移除的最小長度子串以使其成為迴文的問題。我們提供了一個清晰有效的C++實現，它利用簡單的迴圈來迭代字串，建立子串並檢查其迴文狀態，以找到必須移除的子串的最小長度。
透過理解此演算法，您可以應用類似的概念來解決計算機科學和程式設計中的其他字串操作和迴文問題。
562 次瀏覽
