算法设计:缺少字符以组成字符串Pangram

2021年3月14日14:41:02 发表评论 741 次浏览

本文概述

Pangram是包含英文字母中每个字母的句子。给定一个字符串, 找到字符串中缺少的所有字符, 即可以使字符串成为Pangram的字符。我们需要按字母顺序打印输出。

例子:

Input : welcome to lsbin
Output : abdhijnpquvxyz

Input : The quick brown fox jumps
Output : adglvyz

推荐:请尝试使用

{IDE}

首先, 在继续解决方案之前。

我们已经讨论过Pangram检查。这个想法是相似的, 我们遍历给定的字符串并标记所有访问过的字符。最后, 我们打印所有未被访问的字符。

小写和大写字符被认为是相同的。

C ++ 14

// C++ program to find characters that needs
// to be added to make Pangram
#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
 
// Returns characters that needs to be added
// to make str
string missingChars(string str)
{
     // A boolean array to store characters
     // present in string.
     bool present[MAX_CHAR] = { false };
 
     // Traverse string and mark characters
     // present in string.
     for ( int i=0; i<str.length(); i++)
     {
         if (str[i] >= 'a' && str[i] <= 'z' )
             present[str[i]- 'a' ] = true ;
         else if (str[i] >= 'A' && str[i] <= 'Z' )
             present[str[i]- 'A' ] = true ;
     }
 
     // Store missing characters in alphabetic
     // order.
     string res = "" ;
     for ( int i=0; i<MAX_CHAR; i++)
         if (present[i] == false )
             res.push_back(( char )(i+ 'a' ));
 
     return res;
}
 
// Driver program
int main()
{
     string str = "The quick brown fox jumps "
                  "over the dog" ;
     cout << missingChars(str);
     return 0;
}

Java

// Java program to find characters that
// needs to be added to make Pangram
import java.io.*;
import java.util.ArrayList;
 
class GFG{
     
private static ArrayList<Character>missingChars(
     String str, int strLength)
{
     final int MAX_CHARS = 26 ;
     
     // A boolean array to store characters
     // present in string.
     boolean [] present = new boolean [MAX_CHARS];
     ArrayList<Character> charsList = new ArrayList<>();
     
     // Traverse string and mark characters
     // present in string.
     for ( int i = 0 ; i < strLength; i++)
     {
         if ( 'A' <= str.charAt(i) &&
                    str.charAt(i) <= 'Z' )
             present[str.charAt(i) - 'A' ] = true ;
         else if ( 'a' <= str.charAt(i) &&
                         str.charAt(i) <= 'z' )
             present[str.charAt(i) - 'a' ] = true ;
     }
     
     // Store missing characters in alphabetic
     // order.
     for ( int i = 0 ; i < MAX_CHARS; i++)
     {
         if (present[i] == false )
             charsList.add(( char )(i + 'a' ));
     }
     return charsList;
}
 
// Driver Code
public static void main(String[] args)
{
     String str = "The quick brown fox jumps " +
                  "over the dog" ;
                  
     ArrayList<Character> missing = GFG.missingChars(
         str, str.length());
         
     if (missing.size() >= 1 )
     {
         for (Character character : missing)
         {
             System.out.print(character);
         }
     }
}
}
 
// This code is contributed by theSardul

Python3

# Python3 program to find characters
# that needs to be added to make Pangram
MAX_CHAR = 26
 
# Returns characters that needs
# to be added to make str
def missingChars( Str ):
     
     # A boolean array to store characters
     # present in string.
     present = [ False for i in range (MAX_CHAR)]
 
     # Traverse string and mark characters
     # present in string.
     for i in range ( len ( Str )):
         if ( Str [i] > = 'a' and Str [i] < = 'z' ):
             present[ ord ( Str [i]) - ord ( 'a' )] = True
         elif ( Str [i] > = 'A' and Str [i] < = 'Z' ):
             present[ ord ( Str [i]) - ord ( 'A' )] = True
 
     # Store missing characters in alphabetic
     # order.
     res = ""
 
     for i in range (MAX_CHAR):
         if (present[i] = = False ):
             res + = chr (i + ord ( 'a' ))
             
     return res
 
# Driver code
Str = "The quick brown fox jumps over the dog"
 
print (missingChars( Str ))
 
# This code is contributed by avanitrachhadiya2155

输出如下:

alyz

时间复杂度:

上)

辅助空间:

O(1)

木子山

发表评论

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