检查字符串中的字符是否能形成回文（使用O(1)额外空间）

2021年4月3日17:22:11 发表评论 788 次浏览

本文概述

给定一个字符串str。该字符串可能包含小写字母, 特殊字符, 数字甚至空格。任务是检查是否只有字符串中存在的字母形成了回文组合, 而没有使用任何多余的空格。

注意注意：不允许使用额外的空间来解决此问题。此外, 字符串中存在的字母均使用小写字母, 并且字符串中可能包含特殊字符, 数字甚至空格以及小写字母。

例子:

Input : str = “m a 343 la y a l am”
Output : YES
字符串中的字符构成“malayalam”序列，这是一个回文.
Input : str = “malayalam”
Output : YES


方法:

  • 创建两个实用程序函数以获取字符串中出现的字符的第一个和最后一个位置。
  • 开始遍历字符串, 每次都一直查找第一个和最后一个字符的位置。
  • 如果每个迭代的第一个和最后一个字符都相同, 并且字符串被完全遍历, 则打印"是", 否则打印"否"。

下面是上述方法的实现：

C ++

// CPP program to check if the characters in
// the given string forms a Palindrome in
// O(1) extra space
#include <iostream>
using namespace std;
  
// Utilty function to get the position of
// first character in the string
int firstPos(string str, int start, int end)
{
     int firstChar = -1;
  
     // Get the position of first character
     // in the string
     for ( int i = start; i <= end; i++) {
         if (str[i] >= 'a' && str[i] <= 'z' ) {
             firstChar = i;
             break ;
         }
     }
  
     return firstChar;
}
  
// Utilty function to get the position of
// last character in the string
int lastPos(string str, int start, int end)
{
     int lastChar = -1;
  
     // Get the position of last character
     // in the string
     for ( int i = start; i >= end; i--) {
         if (str[i] >= 'a' && str[i] <= 'z' ) {
             lastChar = i;
             break ;
         }
     }
  
     return lastChar;
}
  
// Function to check if the characters in
// the given string forms a Palindrome in
// O(1) extra space
bool isPalindrome(string str)
{
     int firstChar = 0, lastChar = str.length() - 1;
     bool ch = true ;
  
     for ( int i = 0; i < str.length(); i++) {
         firstChar = firstPos(str, firstChar, lastChar);
         lastChar = lastPos(str, lastChar, firstChar);
  
         // break, when all letters are checked
         if (lastChar < 0 || firstChar < 0)
             break ;
         if (str[firstChar] == str[lastChar]) {
             firstChar++;
             lastChar--;
             continue ;
         }
  
         // if mismatch found, break the loop
         ch = false ;
         break ;
     }
  
     return (ch);
}
  
// Driver code
int main()
{
     string str = "m     a  343 la y a l am" ;
     if (isPalindrome(str))
         cout << "YES" ;
     else
         cout << "NO" ;
  
     return 0;
}

Java

// Java program to check if 
// the characters in the given
// string forms a Palindrome 
// in O(1) extra space
import java.io.*;
  
class GFG 
{
  
// Utilty function to get 
// the position of first
// character in the string
static int firstPos(String str, int start, int end)
{
     int firstChar = - 1 ;
      
     // Get the position of 
     // first character in
     // the string
     for ( int i = start; i <= end; i++)
     {
         if (str.charAt(i) >= 'a' && 
         str.charAt(i) <= 'z' )
         {
             firstChar = i;
             break ;
         }
     }
      
     return firstChar;
}
  
// Utilty function to get 
// the position of last 
// character in the string
static int lastPos(String str, int start, int end)
{
     int lastChar = - 1 ;
      
     // Get the position of last 
     // character in the string
     for ( int i = start; i >= end; i--)
     {
         if (str.charAt(i) >= 'a' && 
         str.charAt(i) <= 'z' )
         {
             lastChar = i;
             break ;
         }
     }
      
     return lastChar;
}
  
// Function to check if the 
// characters in the given 
// string forms a Palindrome 
// in O(1) extra space
static boolean isPalindrome(String str)
{
     int firstChar = 0 , lastChar = str.length() - 1 ;
     boolean ch = true ;
  
     for ( int i = 0 ; i < str.length(); i++) 
     {
         firstChar = firstPos(str, firstChar, lastChar);
         lastChar = lastPos(str, lastChar, firstChar);
  
         // break, when all 
         // letters are checked
         if (lastChar < 0 || firstChar < 0 )
             break ;
         if (str.charAt(firstChar) == 
             str.charAt(lastChar)) 
         {
             firstChar++;
             lastChar--;
             continue ;
         }
          
         // if mismatch found, // break the loop
         ch = false ;
         break ;
     }
  
         return ch;
  
}
  
// Driver code
public static void main (String[] args) 
{
     String str = "m a 343 la y a l am" ;
      
     if (isPalindrome(str))
         System.out.print( "YES" );
     else
     System.out.println( "NO" );
}
}
  
// This code is contributed 
// by inder_verma.

Python 3

# Python 3 program to check if the characters 
# in the given string forms a Palindrome in
# O(1) extra space
  
# Utilty function to get the position of
# first character in the string
def firstPos( str , start, end):
  
     firstChar = - 1
  
     # Get the position of first character
     # in the string
     for i in range (start, end + 1 ):
         if ( str [i] > = 'a' and str [i] < = 'z' ) :
             firstChar = i
             break
  
     return firstChar
  
# Utilty function to get the position of
# last character in the string
def lastPos( str , start, end):
  
     lastChar = - 1
  
     # Get the position of last character
     # in the string
     for i in range (start, end - 1 , - 1 ) :
         if ( str [i] > = 'a' and str [i] < = 'z' ) :
             lastChar = i
             break
  
     return lastChar
  
# Function to check if the characters in
# the given string forms a Palindrome in
# O(1) extra space
def isPalindrome( str ):
  
     firstChar = 0
     lastChar = len ( str ) - 1
     ch = True
  
     for i in range ( len ( str )) :
         firstChar = firstPos( str , firstChar, lastChar);
         lastChar = lastPos( str , lastChar, firstChar);
  
         # break, when all letters are checked
         if (lastChar < 0 or firstChar < 0 ):
             break
         if ( str [firstChar] = = str [lastChar]):
             firstChar + = 1
             lastChar - = 1
             continue
  
         # if mismatch found, break the loop
         ch = False
         break
  
     return (ch)
  
# Driver code
if __name__ = = "__main__" :
      
     str = "m     a 343 la y a l am"
     if (isPalindrome( str )):
         print ( "YES" )
     else :
         print ( "NO" )
  
# This code is contributed by ita_c

C#

// C# program to check if 
// the characters in the given
// string forms a Palindrome 
// in O(1) extra space
using System;
  
class GFG 
{
  
// Utilty function to get 
// the position of first
// character in the string
static int firstPos( string str, int start, int end)
{
     int firstChar = -1;
      
     // Get the position of 
     // first character in
     // the string
     for ( int i = start; i <= end; i++)
     {
         if (str[i] >= 'a' && 
            str[i] <= 'z' )
         {
             firstChar = i;
             break ;
         }
     }
      
     return firstChar;
}
  
// Utilty function to get 
// the position of last 
// character in the string
static int lastPos( string str, int start, int end)
{
     int lastChar = -1;
      
     // Get the position of last 
     // character in the string
     for ( int i = start; i >= end; i--)
     {
         if (str[i] >= 'a' && 
            str[i] <= 'z' )
         {
             lastChar = i;
             break ;
         }
     }
      
     return lastChar;
}
  
// Function to check if the 
// characters in the given 
// string forms a Palindrome 
// in O(1) extra space
static bool isPalindrome( string str)
{
     int firstChar = 0, lastChar = str.Length - 1;
     bool ch = true ;
  
     for ( int i = 0; i < str.Length; i++) 
     {
         firstChar = firstPos(str, firstChar, lastChar);
         lastChar = lastPos(str, lastChar, firstChar);
  
         // break, when all 
         // letters are checked
         if (lastChar < 0 || firstChar < 0)
             break ;
         if (str[firstChar] == 
             str[lastChar]) 
         {
             firstChar++;
             lastChar--;
             continue ;
         }
          
         // if mismatch found, // break the loop
         ch = false ;
         break ;
     }
  
         return ch;
}
  
// Driver code
public static void Main () 
{
     string str = "m a 343 la y a l am" ;
      
     if (isPalindrome(str))
         Console.WriteLine( "YES" );
     else
         Console.WriteLine( "NO" );
}
}
  
// This code is contributed 
// by inder_verma.

的PHP

<?php
// PHP program to check if the 
// characters in the given 
// string forms a Palindrome 
// in O(1) extra space
  
// Utilty function to get the 
// position of first character
// in the string
function firstPos( $str , $start , $end )
{
     $firstChar = -1;
  
     // Get the position of first 
     // character in the string
     for ( $i = $start ; $i <= $end ; $i ++) 
     {
         if ( $str [ $i ] >= 'a' and
             $str [ $i ] <= 'z' ) 
         {
             $firstChar = $i ;
             break ;
         }
     }
  
     return $firstChar ;
}
  
// Utilty function to get the 
// position of last character
// in the string
function lastPos( $str , $start , $end )
{
     $lastChar = -1;
  
     // Get the position of last 
     // character in the string
     for ( $i = $start ; $i >= $end ; $i --) 
     {
         if ( $str [ $i ] >= 'a' and 
             $str [ $i ] <= 'z' ) 
         {
             $lastChar = $i ;
             break ;
         }
     }
  
     return $lastChar ;
}
  
// Function to check if the 
// characters in the given 
// string forms a Palindrome 
// in O(1) extra space
function isPalindrome( $str )
{
     $firstChar = 0; 
     $lastChar = count ( $str ) - 1;
     $ch = true;
  
     for ( $i = 0; $i < count ( $str ); $i ++) 
     {
         $firstChar = firstPos( $str , $firstChar , $lastChar );
         $lastChar = lastPos( $str , $lastChar , $firstChar );
  
         // break, when all letters are checked
         if ( $lastChar < 0 or $firstChar < 0)
             break ;
         if ( $str [ $firstChar ] == $str [ $lastChar ])
         {
             $firstChar ++;
             $lastChar --;
             continue ;
         }
  
         // if mismatch found, // break the loop
         $ch = false;
         break ;
     }
  
     return ( $ch );
}
  
// Driver code
$str = "m a 343 la y a l am" ;
if (isPalindrome( $str ))
     echo "YES" ;
else
     echo "NO" ;
  
// This code is contributed 
// by inder_verma.
?>

输出如下：

YES
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: