Question: there are two string A & B which only contain upper case English alphabets. B has smaller length than A. How to quickly decide whether all the characters in B are contained in A. For exmaple,
String A : ABCDEFGHLMNOPQRS
String B : DCGSRQPO
Your method take A and B as input and should return true because All characters in B appeared in A too.
String A : ABCDEFGHLMNOPQRS
String B : DCGSRQPZ
Your method take A and B as input and should return false because character 'Z' appeared in B but in A.
My thought: It's a gernal question like checking whether a word spelling is correct. We can just setup a HashSet of all the characters appeared in A and then go through characters in B to check whether they are in the HashSet. However since the characters are limited to English alphabets, we can a boolean array of length 26 or even use the lowest 26 bits of an Integer to record the appearance of each alphabet
Although boolean array may waste some space ( depends on JVM implementation of boolean type ) , but I think array access should be faster than bit operation
Java Implementation:
public class StringContaining { public static void main(String[] args) { BooleanArray set1 = new BooleanArray(); BitsArray set2 = new BitsArray(); assert contains("ABCDEFGHLMNOPQRS" , "DCGSRQPO" , set1); assert contains("ABCDEFGHLMNOPQRS" , "DCGSRQPO" , set2); assert !contains("ABCDEFGHLMNOPQRS" , "DCGSRQPZ" , set1); assert !contains("ABCDEFGHLMNOPQRS" , "DCGSRQPZ" , set2); } public static boolean contains (String sa, String sb , CharHashSet set) { int i = 0; int size = sa.length(); for (; i < size; i ++ ) { set.add(sa.charAt(i)); } for ( i = 0 , size = sb.length() ; i < size ; i ++ ) { if (! set.contains(sb.charAt(i))) return false; } return true; } public interface CharHashSet { public void add(char c); public boolean contains ( char c); } public static class BooleanArray implements CharHashSet{ private boolean[] exists = new boolean[26]; @Override public void add(char c) { exists[c - 'A'] = true; } @Override public boolean contains(char c) { return exists[c-'A']; } } public static class BitsArray implements CharHashSet{ private int exists; @Override public void add(char c) { exists |= 1 << (c - 'A'); } @Override public boolean contains(char c) { return ( exists & (1 << (c - 'A')) ) > 0; } } }
相关推荐
ntp服务的安装包
这个题目名为"Given-a-string-containing-just-the-characters-and-determine-if-the-input",实际上是在询问我们如何编写一个函数或程序来检查一个字符串是否只包含特定的一组字符。 首先,让我们明确一下问题的...
This file creates a global JSON object containing two methods: stringify and parse. JSON.stringify(value, replacer, space) value any JavaScript value, usually an object or array. replacer an ...
Released under the GPL licence (version 2 or later). Welcome to Squashfs version 2.2-r2. Please see the CHANGES file for details of changes. Squashfs is a highly compressed read-only filesystem for...
这是一个可以傻瓜式一键安装在debian,ubuntu,deepin等linux系统的谷歌浏览器deb格式安装包
instances are considered very large instances containing many pieces with very complex outlines, where continuous rotations may be desired. The Nesting problem is presented, with a description of its ...
quotes ("string with whitespace") If the ParameterName is undefined, the program will be terminated with an error message. 4.2 Decoder <value> #comment The values are read in a ...
Overview Package Class Tree Deprecated Index Help PREV NEXT FRAMES NO FRAMES A B C D E F G H I J L P R S U V ---------------------------------------------------...Returns an Enumeration containing ...
browser360-cn-stable_10.0.2013.1-1_amd64.deb
isn't already one, setting its value to an object containing a stringify method and a parse method. The parse method uses the eval method to do the parsing, guarding it with several regular ...
|__ build/ - Generated directory containing build output binaries. |__ exe/ - Contains sample client application source code. | |__ simple_dma/ - Sample code for AXI-MM configured XDMA IP. | |__ ...
7.13.2. 从 0.9.3 到 1.0.0RC1 或更新的版本的移植 7.13.3. 从 0.9.2 移植到 0.9.3 或更新的版本 7.13.4. 从 0.6.0 移植到 0.8.0 或更新的版本 7.13.5. 从 0.2.0 或以前的版本移植到 0.6.0 8. Zend_Currency ...
The org.apache.struts2.config.Configuration implementation class org.apache.struts2.config.Configuration接口名 struts.configuration.files A list of configuration files automatically loaded by ...
a problem, enter some words related to the problem and appropriate pages will be displayed. Of course, search feature will not help if you enter a question like "how can I use it?". It only finds ...
Extend this program to set up an 8 by 8 square game board containing several different pieces in predefined positions. For each move of the game, the program will choose a piece at random, and move it...
Telerik RadUpload is a suite containing: a highly efficient proprietary HttpModule, which enables uploading of files with size up to 2GB, while allocating a minimum amount of server memory. UI ...
2、脚本重启 3、加载模型:model.load_weights(‘./model.h5’) 4、模型报错:ValueError: You are trying to load a weight file containing 12 layers into a model with 0 layers. 问题分析: 模型创建后还没有...
C#的另一个解析器组合器是一个库用于构建优化和灵活的解析器。 安装 APC#直接嵌入到您的C#程序中,而无需任何其他... Word // Any string containing letters ) . FollowedBy ( Parser . WhiteSpaces . Maybe
Computer Networking: A Top-Down Approach, 6th Edition Solutions to Review Questions and Problems Version Date: May 2012 ...This document contains the solutions to review questions ...Problem 1 There...
"VB_package_text_file_containing_sample_class.rar" 提供了一个VB类(Class A),专门用于处理文本文件的读写操作。在这个压缩包中,我们可以找到相关的源代码示例,帮助我们理解如何在VB中实现这一功能。 类A...