`
leonzhx
  • 浏览: 794119 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Question 2. String Containing Problem

阅读更多

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;
		}
		
	}
	

}

 

0
2
分享到:
评论

相关推荐

    ntp_1%3a4.2.8p10+dfsg-5ubuntu7.3_amd64.deb

    ntp服务的安装包

    Given-a-string-containing-just-the-characters-and-determine-if-the-inpu

    这个题目名为"Given-a-string-containing-just-the-characters-and-determine-if-the-input",实际上是在询问我们如何编写一个函数或程序来检查一个字符串是否只包含特定的一组字符。 首先,让我们明确一下问题的...

    json.js_json2.js

    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 ...

    squashfs2.2-r2.tar.gz

    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...

    谷歌浏览器linux版google-chrome-stable_current_amd64.deb

    这是一个可以傻瓜式一键安装在debian,ubuntu,deepin等linux系统的谷歌浏览器deb格式安装包

    GEOMETRICAL MODELS AND ALGORITHMS FOR IRREGULAR SHAPES PLACEMENT

    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 ...

    avs 标准文档中的源码

    quotes ("string with whitespace") If the ParameterName is undefined, the program will be terminated with an error message. 4.2 Decoder &lt;value&gt; #comment The values are read in a ...

    servlet2.4doc

    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

    browser360-cn-stable_10.0.2013.1-1_amd64.deb

    JSON2.JS JSON.JS JSON_PARSE.JS

    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 ...

    xdma_driver_win_src_2018_2.zip (xilinx pcie dma driver)

    |__ build/ - Generated directory containing build output binaries. |__ exe/ - Contains sample client application source code. | |__ simple_dma/ - Sample code for AXI-MM configured XDMA IP. | |__ ...

    ZendFramework中文文档

    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 ...

    Struts课堂笔记.rar--struts2的struts.properties配置文件详解

    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 ...

    WPF 国际象棋 棋子 ChessProgrammingTest.zip

    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...

    RadControls.for.ASP.NET2.Q1.2007.SP2.RadUpload.Net2.v2.3.2.0

    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 ...

    解决Tensorflow2.0 tf.keras.Model.load_weights() 报错处理问题

    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. 问题分析: 模型创建后还没有...

    APCSharp:C#的另一个解析器组合器

    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_package_text_file_containing_sample_class.rar" 提供了一个VB类(Class A),专门用于处理文本文件的读写操作。在这个压缩包中,我们可以找到相关的源代码示例,帮助我们理解如何在VB中实现这一功能。 类A...

Global site tag (gtag.js) - Google Analytics