Java strings and substrings

Question

hey folks,

Can someone help me with this Java problem?

I want to write a method that takes two strings as arguments and returns true if each character (including space and punctuation) that appears in one string also appears in the other.

Thanks

Answer 1

I'd like to help answer this, but this feels like a programming assignment. You should post some code of what you've attempted and where it's going wrong.

Answer 2

You can take a look at Arrays.binarySearch(char[] array, char searched), String.toCharArray() and Arrays.sort(..) and to check whether all characters of the first string occur in the 2nd.

Answer 3

well to start you off

public bool samestring(string a, string b){
  boolean samestring = false; 

 //compare string a to string b.

}

Do you really want us to write up the logic for you?

Answer 4

You don't specify what do you want us to help you with, nor what do you have so far, so I guess the best thing I could do is to help you to "THINK" how to solve the problem ( to create the algorithm )

From your description I would came up with the following pseudo-code

+ doesEachCharacterIn_A_AppearIn_B?(a : String, b : String ) : boolean 
    // Iterate all the charactes in string "a"
    forEach( character in a, 
       // If one of them doesn't appear in b
       if( character.doesNotAppearIn( b ) ,
            // game over 
            // return false
            return false
       )
    )
    // If after the iteration there wasn't a "false" already
    // it means all of them appeared
    return true

I hope that helps you to get started.

Try modifying your original post and add more details as you get through it.

Answer 5

Are you interested in testing whether the set of characters in the two strings is identical? (i.e. "abba" == "abbb" but "aaa" != "ba") If so, you can do it quite efficiently by:

1) Insert all characters of str1 into a HashSet s1

2) Insert all characters of str2 into a HashSet s2

3) If s1 and s2 differ in their size return false

4) Traverse str2 and check every character against s1

Note:

A) If you deal with ASCII chars only you can use simple arrays instead of hash sets.

B) If you only need to verify that the set of characters of str2 is a subset of the set of characters of str1, you can skip steps 2 and 3

Answer 6

Here is an attempt in C++. Hopefully you will get the idea:

bool hasSameChars(string a, string b)
{
  map<char, int> m;
  for (int i = 0; i < a.size(); ++i) m[a[i]] = 1;
  for (int i = 0; i < b.size(); ++i) m[b[i]]++;
  for (map<char, int>::iterator it = m.begin(); it != m.end(); it++)
  {
    int count = it->second;
    if (count == 1) return false;
  }
  return true;
}

Regards, Rafael.

Answer 7

Depending on your space and time complexity, the solutions may vary. The simplest one, however, and assuming you don't need to write the algorithm, is to add all characters of each to a different set, and then check if both sets include the other, or if the union of both has the same number of elements as each separately.

If you do need to write the algorithm, is there any time and space efficiency requirements? Also, if you do need to write it, you are probably studying something in particular, such as dynamic programming, trees, etc. The solution should go the way of whatever it is that you are studying.

Answer 8

Here's a simple O(N^2) solution:

static boolean in(String s1, String s2) {
   return
      s1.isEmpty() ? true :
      !s2.contains(s1.substring(0, 1)) ? false :
      in(s1.substring(1), s2)
   ;
}

The logic is self-explanatory:

• If s1 is empty, then all characters in s1 appears in s2 by definition
• If s2 does not contain the first character in s1, then the answer is false
• Otherwise check if all of the rest of s1 appear in s2.

Note that in this approach, in("xxx", "x") returns true.

Other things you can do:

• Use a (multi)set data structure to represent a string as a (multi)set of characters that appears in it
  • Then your query is a simple "is subset of" operation (see: Eyal's answer)
• Reorder characters in a string by sorting it to facilitate binary search (see: Bozho's answer)

---

I presume from one of OP's comments that there's also a need for a method to find the longest substring of s1 that consist of only characters that also occur in s2. This is a regex-based solution that assumes that neither s1 nor s2 could contain # to simplify the logic.

static String maximalAllOccurringIn(String s1, String s2) {
    return
       (s1 + "#" + s2)
          .replaceAll(
            "(.)(?!.*#.*\\1)|#.*",
            ""
          )
    ;
}

Note that maximalAllOccurringIn("AaBbCcDd", "BadCode") is "aBCd", and maximalAllOccurringIn("xxyyzz", "yax") is "xxyy".

Since this is homework, I'll leave it to you to study how it works.